Tuesday, March 22, 2016 4:15 pm
-
4:15 pm
EDT (GMT -04:00)
Title: Gallai's path decomposition conjecture
Speaker: | Marthe Bonamy |
Affiliation: | CNRS, LaBRI, Université de Bordeaux, France |
Room: | MC 6486 |
Abstract: Gallai conjectured in 1968 that the edges of any connected graph on n vertices can be decomposed into at most (n+1)/2 paths. We survey existing results, which deal mostly with graphs where odd-degree vertices or even-degree vertices induce specific structures, and confirm that conjecture for all graphs with maximum degree at most five. This is joint work with Thomas Perrett (Technical University of Denmark).