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.