Gallai's path decomposition conjecture for graphs with treewidth at most 3
Fábio Botler, Maycon Sambinelli, Rafael S. Coelho, Orlando Lee · Journal of Graph Theory · 2019
Abstract A path decomposition of a graph is a set of edge‐disjoint paths of that covers the edge set of . Gallai (1968) conjectured that every connected graph with vertices admits a path decomposition of size at most . Gallai's conjecture was verified for many classes of graphs. In particular, Lovász (1968) verified this conjecture for graphs with at most one vertex of even degree, and Pyber (1996) verified it for graphs in which every cycle contains a vertex of odd degree. Recently, Bonamy and Perrett verified Gallai's conjecture for graphs with maximum degree at most 5. In this paper, we verify Gallai's conjecture for graphs with treewidth at most 3. Moreover, we show that the only graphs with treewidth at most 3 that do not admit a path decomposition of size at most are isomorphic to or , the graph obtained from by removing an edge.