Chvátal-Erdős condition for pancyclicity

EUROCOMB’23

Abstract
An $n$-vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices and it is pancyclic if it contains cycles of all lengths from $3$ up to $n$. A celebrated meta-conjecture of Bondy states that every non-trivial condition implying Hamiltonicity also implies pancyclicity (up to possibly a few exceptional graphs). We show that every graph $G$ with $\kappa(G) > (1+o(1)) \alpha(G)$ is pancyclic. This extends the famous Chvátal-Erdős condition for Hamiltonicity and proves asymptotically a $30$-year old conjecture of Jackson and Ordaz.

Pages:
373–379
References

M. Ajtai, J. Komlós, and E. Szemerédi. First occurrence of Hamilton cycles in random graphs. In Cycles in graphs (Burnaby, B.C., 1982), Vol. 115, North-Holland Mathematical Studies, North-Holland, Amsterdam, 115:173-178, 1985.
https://doi.org/10.1016/S0304-0208(08)73007-X

N. Alon and M. Krivelevich. Divisible subdivisions. Journal of Graph Theory, 98(4):623-629, 2021.
https://doi.org/10.1002/jgt.22716

Y. Alon, M. Krivelevich, and E. Lubetzky. Cycle lengths in sparse random graphs. Random Structures & Algorithms, 61(3):444-461, 2022.
https://doi.org/10.1002/rsa.21067

D. Amar, I. Fournier, and A. Germa. Pancyclism in Chvátal-Erdős graphs. Graphs and Combinatorics, 7(2):101-112, 1991.
https://doi.org/10.1007/BF01788136

D. Bauer and E. Schmeichel. Hamiltonian degree conditions which imply a graph is pancyclic. Journal of Combinatorial Theory, Series B, 48(1):111-116, 1990.
https://doi.org/10.1016/0095-8956(90)90133-K

J. A. Bondy. Pancyclic graphs: recent results, infinite and finite sets. In Colloq. Math. Soc. János Bolyai, Keszthely, pp. 181-187, 1973.

J. A. Bondy. Pancyclic graphs I. Journal of Combinatorial Theory, Series B, 11(1):80-84, 1971.
https://doi.org/10.1016/0095-8956(71)90016-5

J. A. Bondy. Longest paths and cycles in graphs of high degree. Department of Combinatorics and Optimization, University of Waterloo, 1980.

J. A. Bondy and M. Simonovits. Cycles of even length in graphs. J. Combinatorial Theory B 16 (1974) 97-105.
https://doi.org/10.1016/0095-8956(74)90052-5

V. Chvátal. On Hamilton's ideals. Journal of Combinatorial Theory, Series B, 12(2):163-168, 1972.
https://doi.org/10.1016/0095-8956(72)90020-2

V. Chvátal and P. Erdős. A note on Hamiltonian circuits. Discrete Mathematics, 2(2):111-113, 1972.
https://doi.org/10.1016/0012-365X(72)90079-9

B. Csaba, D. Kühn, A. Lo, D. Osthus, and A. Treglown. Proof of the 1-factorization and Hamilton decomposition conjectures. Memoirs of the American Mathematical Society, 244, monograph 1154, 170 pages, 2016.
https://doi.org/10.1090/memo/1154

B. Cuckler and J. Kahn. Hamiltonian cycles in Dirac graphs. Combinatorica, 29(3):299-326, 2009.
https://doi.org/10.1007/s00493-009-2360-2

G. A. Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, 3(1):69-81, 1952.
https://doi.org/10.1112/plms/s3-2.1.69

N. Draganić, D. Munhá Correia and B. Sudakov. Pancyclicity of Hamiltonian graphs. arXiv:2209.03325 2022.

P. Erdős. Some problems in graph theory. In Hypergraph Seminar, pp. 187-190. Springer, 1972.
https://doi.org/10.1007/BFb0066194

P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp. On cycle-complete graph Ramsey numbers. Journal of Graph Theory, 2(1):53-64, 1978. Chvátal-Erdős condition for pancyclicity 7
https://doi.org/10.1002/jgt.3190020107

G. H. Fan. New sufficient conditions for cycles in graphs. Journal of Combinatorial Theory, Series B, 37(3):221-227, 1984.
https://doi.org/10.1016/0095-8956(84)90054-6

A. Ferber, E. Long, and B. Sudakov. Counting Hamilton decompositions of oriented graphs. International Mathematics Research Notices, 2018(22):6908-6933, 2018.
https://doi.org/10.1093/imrn/rnx085

L. Friedman and M. Krivelevich. Cycle lengths in expanding graphs. Combinatorica, 41(1):53-74, 2021.
https://doi.org/10.1007/s00493-020-4434-0

R. J. Gould. Recent advances on the Hamiltonian problem: Survey III. Graphs and Combinatorics, 30(1):1-46, 2014.
https://doi.org/10.1007/s00373-013-1377-x

H. Liu and R. Montgomery. A solution to Erdős and Hajnal's odd cycle problem. Journal of the American Mathematical Society, to appear. B. Jackson and O. Ordaz. Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey. Discrete mathematics, 84(3):241-254, 1990.
https://doi.org/10.1016/0012-365X(90)90130-A

P. Keevash, E. Long, and J. Skokan. Cycle-complete Ramsey numbers. International Mathematics Research Notices, 2021(1):275-300, 2021.
https://doi.org/10.1093/imrn/rnz119

P. Keevash and B. Sudakov. Pancyclicity of Hamiltonian and highly connected graphs. Journal of Combinatorial Theory, Series B, 100(5):456-467, 2010.
https://doi.org/10.1016/j.jctb.2010.02.001

M. Krivelevich. The critical bias for the Hamiltonicity game is (1 + o(1))n/ ln n. Journal of the American Mathematical Society, 24(1):125-131, 2011.
https://doi.org/10.1090/S0894-0347-2010-00678-9

M. Krivelevich, C. Lee, and B. Sudakov. Robust Hamiltonicity of Dirac graphs. Transactions of the American Mathematical Society, 366(6):3095-3130, 2014.
https://doi.org/10.1090/S0002-9947-2014-05963-1

D. Kühn and D. Osthus. Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments. Advances in Mathematics, 237:62-146, 2013.
https://doi.org/10.1016/j.aim.2013.01.005

C.-H. Liu and J. Ma. Cycle lengths and minimum degree of graphs. Journal of Combinatorial Theory, Series B, 128:66-95, 2018.
https://doi.org/10.1016/j.jctb.2017.08.002

D. Kühn and D. Osthus. Hamilton cycles in graphs and hypergraphs: an extremal perspective. In Proceedings of the International Congress of Mathematicians-Seoul 2014. Vol. IV, pp. 381-406. Kyung Moon Sa, Seoul, 2014.

K. G. Milans, F. Pfender, D. Rautenbach, F. Regen, and D. B. West. Cycle spectra of Hamiltonian graphs. Journal of Combinatorial Theory, Series B, 102(4):869-874, 2012.
https://doi.org/10.1016/j.jctb.2012.04.002

L. Pósa, Hamiltonian circuits in random graphs. Discrete Mathematics, 14(4):359-364, 1976.
https://doi.org/10.1016/0012-365X(76)90068-6

A. Saito, Chvátal-Erdős theorem: Old theorem with new aspects In Kyoto International Conference on Computational Geometry and Graph Theory, pp. 191-200. Springer, 2007.
https://doi.org/10.1007/978-3-540-89550-3_21

E. F. Schmeichel and S. L. Hakimi. A cycle structure theorem for Hamiltonian graphs. Journal of Combinatorial Theory, Series B, 45(1):99-107, 1988.
https://doi.org/10.1016/0095-8956(88)90058-5

J. Verstraëte. Extremal problems for cycles in graphs. In Recent trends in combinatorics, pp. 83-116. Springer, 2016.
https://doi.org/10.1007/978-3-319-24298-9_4

Metrics

0

Views

0

PDF views