On Gallai’s path decomposition conjecture

Abstract

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 dF (v) ≤ 3 for every vertex v ∈ V (F)\{x, y}, then G has a path-decomposition D1 such that |D1| ≤ (n+1)/2 and D1(x) ≥ 2, and a path-decomposition D2 such that |D2| ≤ (n+1)/2 and D2(y) ≥ 2.