Gallai’s path decomposition conjecture

Series: 
Graph Theory Working Seminar
Wednesday, September 12, 2018 - 4:30pm
1 hour (actually 50 minutes)
Location: 
Skiles 006
,  
Georgia Tech
Organizer: 
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.