2025/10/04 by Yanan Chu, Yan Wang, Chu, Yanan +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2510.12806
openalex publication_date 2025/10/04 · openalex created_date 2025/10/17 · openalex updated_date 2026/07/28
Gallai's conjecture asserts that every connected graph on n vertices can be decomposed into (n+1)/(2) paths. For general graphs (possibly disconnected), it was proved that every graph on n vertices can be decomposed into (2n)/(3) paths. This is also best possible (consider the graphs consisting of vertex-disjoint triangles). Lovász showed that every n-vertex graph with at most one vertex of even degree can be decomposed into (n)/(2) paths. However, Gallai's conjecture is difficult for graphs with many vertices of even degrees. Favaron and Kouider verified Gallai's conjecture for all Eulerian graphs with maximum degree at most 4. In this paper, we show if G is an Eulerian graph on n ≥ 4 vertices and the distance between any two triangles in G is at least 3, then G can be decomposed into at most (3n)/(5) paths.