Gallai’s path decomposition conjecture

Graph Theory Working Seminar
Wednesday, September 12, 2018 - 4:30pm
1 hour (actually 50 minutes)
Skiles 006
Georgia Tech
Gallai conjectured in 1968 that the edges of a connected graph on n vertices can be decomposed into at most (n+1)/2 edge-disjoint paths. This conjecture is still open, even for planar graphs. In this talk we will discuss some related results and special cases where it is known to hold.