Towards the Erdős-Gallai cycle decomposition conjecture. (English) Zbl 1531.05195
Summary: In the 1960’s, Erdős and Gallai conjectured that the edges of any \(n\)-vertex graph can be decomposed into \(O(n)\) cycles and edges. We improve upon the previous best bound of \(O(n \log \log n)\) cycles and edges due to D. Conlon et al. [Random Struct. Algorithms 45, No. 4, 608–626 (2014; Zbl 1328.05146)], by showing an \(n\)-vertex graph can always be decomposed into \(O(n \log^\star n)\) cycles and edges, where \(\log^\star n\) is the iterated logarithm function.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C38 | Paths and cycles |
References:
| [1] | Aharoni, R.; Haxell, P., Hall’s theorem for hypergraphs. J. Graph Theory, 2, 83-88 (2000) · Zbl 0956.05075 |
| [2] | Alon, N.; Spencer, J. H., The Probabilistic Method (2016), John Wiley & Sons · Zbl 1333.05001 |
| [3] | Awerbuch, B.; Luby, M.; Goldberg, A.; Plotkin, S., Network decomposition and locality in distributed computation, 364-369 |
| [4] | Ben-Eliezer, I.; Krivelevich, M.; Sudakov, B., Long cycles in subgraphs of (pseudo)random directed graphs. J. Graph Theory, 3, 284-296 (2012) · Zbl 1244.05195 |
| [5] | Blanché, A.; Bonamy, M.; Bonichon, N., Gallai’s path decomposition for planar graphs, 758-764 |
| [6] | Bondy, J. A., Small cycle double covers of graphs, 21-40 · Zbl 0734.05067 |
| [7] | Broder, A. Z.; Frieze, A. M.; Suen, S.; Upfal, E., An efficient algorithm for the vertex-disjoint paths problem in random graphs, 261-268 · Zbl 0852.68036 |
| [8] | Chakraborti, D.; Kim, J.; Kim, J.; Kim, M.; Liu, H., Well-mixing vertices and almost expanders. Proc. Am. Math. Soc., 12, 5097-5110 (2022) · Zbl 1498.05247 |
| [9] | Chung, F. R.K., On the coverings of graphs. Discrete Math., 2, 89-93 (1980) · Zbl 0451.05037 |
| [10] | Colbourn, C. J.; van Oorschot, P. C., Applications of combinatorial designs in computer science. ACM Comput. Surv., 2, 223-250 (jun 1989) |
| [11] | Conlon, D.; Fox, J.; Sudakov, B., Cycle packing. Random Struct. Algorithms, 4, 608-626 (2014) · Zbl 1328.05146 |
| [12] | Dean, N., What is the smallest number of dicycles in a dicycle decomposition of an Eulerian digraph?. J. Graph Theory, 3, 299-308 (1986) · Zbl 0607.05049 |
| [13] | Dean, N.; Kouider, M., Gallai’s conjecture for disconnected graphs. Discrete Math., 1-3, 43-54 (2000) · Zbl 0943.05067 |
| [14] | Erdős, P., Some unsolved problems in graph theory and combinatorial analysis, 97-109 · Zbl 0221.05051 |
| [15] | Erdős, P., Problems and results in combinatorial analysis, 3-17 · Zbl 0361.05037 |
| [16] | Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica, 1, 25-42 (1981) · Zbl 0486.05001 |
| [17] | Erdős, P., On some of my conjectures in number theory and combinatorics, 3-19 · Zbl 0539.05001 |
| [18] | Erdős, P.; Goodman, A. W.; Pósa, L., The representation of a graph by set intersections. Can. J. Math., 106-112 (1966) · Zbl 0137.43202 |
| [19] | Fan, G., Subgraph coverings and edge switchings. J. Comb. Theory, Ser. B, 1, 54-83 (2002) · Zbl 1031.05104 |
| [20] | Fan, G., Covers of Eulerian graphs. J. Comb. Theory, Ser. B, 2, 173-187 (2003) · Zbl 1031.05105 |
| [21] | Fernández, I. G.; Liu, H., How to build a pillar: a proof of Thomassen’s conjecture. J. Comb. Theory, Ser. B, 13-33 (2023) · Zbl 1519.05143 |
| [22] | Gil Fernández, I.; Kim, J.; Kim, Y.; Liu, H., Nested cycles with no geometric crossings. Proc. Am. Math. Soc., Ser. B, 03, 22-32 (2022) · Zbl 1482.05172 |
| [23] | Girão, A.; Granet, B.; Kühn, D.; Osthus, D., Path and cycle decompositions of dense graphs. J. Lond. Math. Soc. (2021) · Zbl 1479.05300 |
| [24] | Glebov, R., On Hamilton cycles and other spanning structures (2013), Freie Universität Berlin, PhD thesis |
| [25] | Glock, S.; Kühn, D.; Osthus, D., Optimal path and cycle decompositions of dense quasirandom graphs. J. Comb. Theory, Ser. B, 88-108 (2016) · Zbl 1332.05078 |
| [26] | Haslegrave, J.; Hu, J.; Kim, J.; Liu, H.; Luan, B.; Wang, G., Crux and long cycles in graphs. SIAM J. Discrete Math., 4, 2942-2958 (2022) · Zbl 1512.05235 |
| [27] | Haslegrave, J.; Hyde, J.; Kim, J.; Liu, H., Ramsey numbers of cycles versus general graphs. Forum Math. Sigma, e10 (2023) · Zbl 1508.05111 |
| [28] | Haslegrave, J.; Kim, J.; Liu, H., Extremal density for sparse minors and subdivisions. Int. Math. Res. Not. (2021) · Zbl 07912960 |
| [29] | Haxell, P. E., Tree embeddings. J. Graph Theory, 3, 121-130 (2001) · Zbl 0967.05029 |
| [30] | Hoory, S.; Linial, N.; Wigderson, A., Expander graphs and their applications. Bull. Am. Math. Soc. (N.S.), 4, 439-561 (2006) · Zbl 1147.68608 |
| [31] | Jiang, T.; Methuku, A.; Yepremyan, L., Rainbow Turán number of clique subdivisions. Eur. J. Comb. (2023) · Zbl 1512.05197 |
| [32] | Jukna, S., On graph complexity. Comb. Probab. Comput., 6, 855-876 (2006) · Zbl 1160.68480 |
| [33] | Kim, J.; Liu, H.; Sharifzadeh, M.; Staden, K., Proof of Komlós’s conjecture on Hamiltonian subsets. Proc. Lond. Math. Soc. (3), 5, 974-1013 (2017) · Zbl 1378.05116 |
| [34] | Komlós, J.; Szemerédi, E., Topological cliques in graphs. Comb. Probab. Comput., 2, 247-256 (1994) · Zbl 0809.05080 |
| [35] | Komlós, J.; Szemerédi, E., Topological cliques in graphs II. Comb. Probab. Comput., 1, 79-90 (1996) · Zbl 0846.05023 |
| [36] | Korándi, D.; Krivelevich, M.; Sudakov, B., Decomposing random graphs into few cycles and edges. Comb. Probab. Comput., 6, 857-872 (2015) · Zbl 1371.05150 |
| [37] | Krivelevich, M., Long cycles in locally expanding graphs, with applications. Combinatorica, 1, 135-151 (2019) · Zbl 1438.05142 |
| [38] | Letzter, S., Separating paths systems of almost linear size (2022), preprint |
| [39] | Letzter, S.; Girão, A., Immersion of complete digraphs in Eulerian digraphs. Isr. J. Math. (2023), in press |
| [40] | Liu, H.; Montgomery, R., A proof of Mader’s conjecture on large clique subdivisions in \(C_4\)-free graphs. J. Lond. Math. Soc. (2), 1, 203-222 (2017) · Zbl 1370.05103 |
| [41] | Liu, H.; Montgomery, R., A solution to Erdős and Hajnal’s odd cycle problem. J. Am. Math. Soc., 4, 1191-1234 (2023) · Zbl 1519.05136 |
| [42] | Liu, H.; Wang, G.; Yang, D., Clique immersion in graphs without a fixed bipartite graph. J. Comb. Theory, Ser. B, 346-365 (2022) · Zbl 1497.05183 |
| [43] | Lovász, L., On covering of graphs, 231-236 · Zbl 0157.31202 |
| [44] | Lucas, É., Récréations mathématiques, vol. 2 (1883), Gauthier-Villars |
| [45] | Montgomery, R., Logarithmically small minors and topological minors. J. Lond. Math. Soc., 1, 71-88 (2015) · Zbl 1307.05209 |
| [46] | Montgomery, R., Spanning cycles in random directed graphs (2021), preprint |
| [47] | Pyber, L., An Erdős—Gallai conjecture. Combinatorica, 1, 67-79 (1985) · Zbl 0581.05043 |
| [48] | Pyber, L., Covering the edges of a graph by …, 583-610 · Zbl 0792.05110 |
| [49] | Pyber, L., Covering the edges of a connected graph by paths. J. Comb. Theory, Ser. B, 1, 152-159 (1996) · Zbl 0840.05071 |
| [50] | Shapira, A.; Sudakov, B., Small complete minors above the extremal edge density. Combinatorica, 1, 75-94 (2015) · Zbl 1363.05241 |
| [51] | Sudakov, B.; Tomon, I., The extremal number of tight cycles. Int. Math. Res. Not., 13, 9663-9684 (2022) · Zbl 1492.05070 |
| [52] | Tomon, I., Robust (rainbow) subdivisions and simplicial cycles (2022), preprint |
| [53] | Veblen, O., An application of modular equations in analysis situs. Ann. Math. (2), 1-4, 86-94 (1912/1913) · JFM 43.0574.01 |
| [54] | Veblen, O., The Cambridge colloquium, 1916, Part II. Bull. Am. Math. Soc., 357-358 (1924), Analysis situs |
| [55] | Wang, Y., Rainbow clique subdivisions (2022), preprint |
| [56] | Yan, L., On path decompositions of graphs (1998), Arizona State University, PhD thesis |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
