2025/09/02 by Saieed Akbari, Akbari, Saieed, Jonny Aloni +5
Computer Science · Mathematics · #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #Commutative Algebra and Its Applications #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2509.01901
openalex publication_date 2025/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An old conjecture of Erdős and Gallai states that every n vertex graph can be decomposed, that is E(G) can be partitioned, into O(n) cycles and edges. The covering version of this conjecture was proven by Pyber in 1985, where it was shown that all graphs can be covered by n-1 cycles and edges. The best upper bound on the number of cycles and edges required to decompose any graph is O(nlog^*(n)), which was recently shown by Bucić and Montgomery in 2023. Here log^*(n) denotes the iterated logarithm function. Meanwhile, a construction of Erdős demonstrate that there exists graphs which require ((3)/(2)-o(1))n cycles and edges to be decomposed. We prove all graphs with maximum degree at most 4 can be decomposed into n-1 or fewer cycles and edges. We also show that every n vertex claw-free graph can be decomposed into n-1 or fewer 2-regular subgraphs and edges. Finally, we prove that every graph G containing a cycle can be covered by n-2 or fewer cycles and edges. This improves Pyber's covering theorem by proving that n-1 cycles and edges are required only for trees.