On Gallai's path decomposition conjecture


Mengmeng Xie




Gallai conjectured that every connected graph on n vertices can be decomposed into at most n+1 2 paths. Let G be a connected graph on n vertices. The E-subgraph of G, denoted by F, is the subgraph induced by the vertices of even degree in G. The maximum degree of G is denoted by △(G). In 2020, Botler and Sambinelli verified Gallai's Conjecture for graphs whose E-subgraphs F satisfy △(F) ≤ 3. If the E-subgraph of G has at most one vertex with degree greater than 3, Fan, Hou and Zhou verified Gallai's Conjecture for G. In this paper, it is proved that if there are two adjacent vertices x, y ∈ V(F) such that d F (v) ≤ 3 for every vertex v ∈ V(F)\{x, y}, then G has a path-decomposition D 1 such that |D 1 | ≤ n+1 2 and D 1 (x) ≥ 2, and a path-decomposition D 2 such that |D 2 | ≤ n+1 2 and D 2 (y) ≥ 2.