×

Cycle lengths and minimum degree of graphs. (English) Zbl 1375.05152

Summary: There has been extensive research on cycle lengths in graphs with large minimum degree. In this paper, we obtain several results that are tight in this area. Let \(G\) be a graph with minimum degree at least \(k+1\). We prove that if \(G\) is bipartite, then there are \(k\) cycles in \(G\) whose lengths form an arithmetic progression with common difference two. For a general graph \(G\), we show that \(G\) contains \(\lfloor k/2\rfloor\) cycles with consecutive even lengths and \(k-3\) cycles whose lengths form an arithmetic progression with common difference one or two. In addition, if \(G\) is 2-connected and non-bipartite, then \(G\) contains \(\lfloor k/2\rfloor\) cycles with consecutive odd lengths.
C. Thomassen [J. Graph Theory 7, 261–271 (1983; Zbl 0515.05052)] made two conjectures on cycle lengths modulo a fixed integer \(k\): (1) every graph with minimum degree at least \(k+1\) contains cycles of all even lengths modulo \(k\); (2) every 2-connected non-bipartite graph with minimum degree at least \(k+1\) contains cycles of all lengths modulo \(k\). These two conjectures, if true, are best possible. Our results confirm both conjectures when \(k\) is even. When \(k\) is odd, we show that minimum degree at least \(k+4\) suffices. This improves all previous results in this direction. Moreover, our results derive new upper bounds of the chromatic number in terms of the longest sequence of cycles with consecutive (even or odd) lengths.

MSC:

05C38 Paths and cycles
05C07 Vertex degrees
05C35 Extremal problems in graph theory

Citations:

Zbl 0515.05052
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N., The largest cycle of a graph with a large minimal degree, J. Graph Theory, 10, 123-127 (1986) · Zbl 0592.05042
[2] Bollobás, B., Cycles modulo k, Bull. Lond. Math. Soc., 9, 97-98 (1977) · Zbl 0348.05104
[3] Bollobás, B.; Häggkvist, R., The circumference of a graph with given minimal degree, (Baker, A.; Bollobás, B.; Hajnal, A., A Tribute to Paul Erdős (1989), Cambridge University Press)
[4] Bondy, J. A., Pancyclic graphs I, J. Combin. Theory Ser. B, 11, 80-84 (1971) · Zbl 0183.52301
[5] Bondy, J.-A.; Murty, U. S.R., Graph Theory, Graduate Texts in Mathematics, vol. 244 (2008), Springer: Springer New York, xii+651 pp · Zbl 1134.05001
[6] Bondy, J. A.; Simonovits, M., Cycles of even length in graphs, J. Combin. Theory Ser. B, 16, 97-105 (1974) · Zbl 0283.05108
[7] Bondy, J. A.; Vince, A., Cycles in a graph whose lengths differ by one or two, J. Graph Theory, 27, 11-15 (1998) · Zbl 0894.05035
[8] Brandt, S.; Faudree, R.; Goddard, W., Weakly pancyclic graphs, J. Graph Theory, 27, 141-176 (1998) · Zbl 0927.05045
[9] Chen, Z.; Ma, J.; Zang, W., Coloring digraphs with forbidden cycles, J. Combin. Theory Ser. B, 115, 210-223 (2015) · Zbl 1319.05050
[10] Chen, G.; Saito, A., Graphs with a cycle of length divisible by three, J. Combin. Theory Ser. B, 60, 277-292 (1994) · Zbl 0799.05036
[11] Dean, N.; Lesniak, L.; Saito, A., Cycles of length 0 modulo 4 in graphs, Discrete Math., 121, 37-49 (1993) · Zbl 0791.05064
[12] Dirac, G. A., Some theorems on abstract graphs, Proc. Lond. Math. Soc., 2, 69-81 (1952) · Zbl 0047.17001
[13] Diwan, A., Cycles of even lengths modulo k, J. Graph Theory, 65, 246-252 (2010) · Zbl 1238.05150
[14] Diwan, A.; Kenkre, S.; Vishwanathan, S., Circumference, chromatic number and online coloring, Combinatorica, 33, 319-334 (2013) · Zbl 1313.05115
[15] Erdős, P., Some recent problems and results in graph theory, combinatorics, and number theory, (Proc. Seventh S-E Conf. Combinatorics, Graph Theory and Computing. Proc. Seventh S-E Conf. Combinatorics, Graph Theory and Computing, Winnipeg. Proc. Seventh S-E Conf. Combinatorics, Graph Theory and Computing. Proc. Seventh S-E Conf. Combinatorics, Graph Theory and Computing, Winnipeg, Utilitas Math. (1976)), 3-14
[16] Erdős, P., Some of my favourite problems in various branches of combinatorics, Matematiche (Catania), 47, 231-240 (1992) · Zbl 0797.05001
[17] Erdős, P., Some of my favorite solved and unsolved problems in graph theory, Quaest. Math., 16, 333-350 (1993) · Zbl 0794.05054
[18] Erdős, P.; Faudree, R.; Gyárfás, A.; Schelp, R., Odd cycles in graphs of given minimum degree, (Graph Theory, Combinatorics, and Applications, vol. 1. Graph Theory, Combinatorics, and Applications, vol. 1, Kalamazoo, MI, 1988 (1991), Wiley-Interscience Publications, Wiley: Wiley-Interscience Publications, Wiley New York), 407-418 · Zbl 0840.05050
[19] Erdős, P.; Hajnal, A., On chromatic numbers of graphs and set systems, Acta Math. Sci. Hungar., 17, 61-99 (1966) · Zbl 0151.33701
[20] Fan, G., Distribution of cycle lengths in graphs, J. Combin. Theory Ser. B, 84, 187-202 (2002) · Zbl 1030.05066
[21] Gyárfás, A., Graphs with \(k\) odd cycle lengths, Discrete Math., 103, 41-48 (1992) · Zbl 0773.05072
[22] Gould, R.; Haxell, P.; Scott, A., A note on cycle lengths in graphs, Graphs Combin., 18, 491-498 (2002) · Zbl 1009.05079
[23] Häggkvist, R., Odd cycles of specified length in nonbipartite graphs, (Graph Theory. Graph Theory, Cambridge, 1981. Graph Theory. Graph Theory, Cambridge, 1981, North-Holland Math. Stud., vol. 62 (1982), North-Holland: North-Holland Amsterdam, New York), 89-99
[24] Häggkvist, R.; Scott, A., Arithmetic Progressions of Cycles (1998), Matematiska Institutionen: Matematiska Institutionen UmeåUniversitet, Technical Report, No. 16
[25] R. Häggkvist, A. Scott, Cycles of nearly equal length in cubic graphs, Preprint.; R. Häggkvist, A. Scott, Cycles of nearly equal length in cubic graphs, Preprint.
[26] Kostochka, A.; Sudakov, B.; Verstraëte, J., Cycles in triangle-free graphs of large chromatic number, Combinatorica, 37, 3, 481-494 (2017) · Zbl 1399.05076
[27] Krusenstjerna-Hafstrøm, U.; Toft, B., Special subdivisions of \(K_4\) and 4-chromatic graphs, Monatsh. Math., 89, 101-110 (1980) · Zbl 0421.05025
[28] Ma, J., Cycles with consecutive odd lengths, European J. Combin., 52, 74-78 (2016) · Zbl 1327.05175
[29] Mihók, P.; Schiermeyer, I., Cycle lengths and chromatic number of graphs, Discrete Math., 286, 147-149 (2004) · Zbl 1055.05060
[30] Nikiforov, V.; Schelp, R., Paths and cycles in graph of large minimal degree, J. Graph Theory, 47, 39-52 (2004) · Zbl 1061.05050
[31] Nikiforov, V.; Schelp, R., Cycle lengths in graphs with large minimum degree, J. Graph Theory, 52, 157-170 (2006) · Zbl 1091.05036
[32] Sudakov, B.; Verstraëte, J., Cycle lengths in sparse graphs, Combinatorica, 28, 357-372 (2008) · Zbl 1174.05065
[33] Sudakov, B.; Verstraëte, J., The extremal function for cycles of length \(l\) mod \(k\), Electron. J. Combin., 24, 1, Article #P1.7 pp. (2017) · Zbl 1355.05143
[34] Thomassen, C., Graph decomposition with applications to subdivisions and path systems modulo k, J. Graph Theory, 7, 261-271 (1983) · Zbl 0515.05052
[35] Thomassen, C., Paths, circuits and subdivisions, (Beineke, L.; Wilson, R., Selected Topics in Graph Theory, vol. 3 (1988), Academic Press), 97-131 · Zbl 0659.05062
[36] Thomassen, C.; Toft, B., Non-separating induced cycles in graphs, J. Combin. Theory Ser. B, 31, 199-224 (1981) · Zbl 0456.05039
[37] Verstraëte, J., On arithmetic progressions of cycle lengths in graphs, Combin. Probab. Comput., 9, 369-373 (2000) · Zbl 0978.05043
[38] Voss, H.; Zuluaga, C., Maximale gerade und ungerade Kreise in Graphen I, Wiss. Z. - Tech. Hochsch. Ilmenau, 23, 57-70 (1977), (German) · Zbl 0366.05039
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.