Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2509.01901 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916938747215872 |
|---|---|
| author | Akbari, Saieed Aloni, Jonny Beikmohammadi, Arash Clow, Alexander |
| author_facet | Akbari, Saieed Aloni, Jonny Beikmohammadi, Arash Clow, Alexander |
| contents | 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(n\log^*(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 $(\frac{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_01901 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Bounds for Cycle-Edge Decompositions and Covers Akbari, Saieed Aloni, Jonny Beikmohammadi, Arash Clow, Alexander Combinatorics 05C70 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(n\log^*(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 $(\frac{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. |
| title | Tight Bounds for Cycle-Edge Decompositions and Covers |
| topic | Combinatorics 05C70 |
| url | https://arxiv.org/abs/2509.01901 |