A generalization of Bondy’s pancyclicity theorem
EUROCOMB’23
368–372
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. 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.
M. Bucić, L. Gishboliner, and B. Sudakov. Cycles of many lengths in Hamiltonian graphs. Forum of Mathematics, Sigma, 10, E70, 2022.
https://doi.org/10.1017/fms.2022.42
M. Chen Hamilton-connected, vertex-pancyclic and bipartite holes. Discrete Mathematics, 345(12):113158, 2022.
https://doi.org/10.1016/j.disc.2022.113158
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. Chvátal-Erdős condition for pancyclicity. arXiv:2301.10190 2023.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-052
N. Draganić, D. Munhá Correia and B. Sudakov. Pancyclicity of Hamiltonian graphs. arXiv:2209.03325 2022.
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. arXiv preprint arXiv:2010.15802, 2020.
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 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 and B. Sudakov. Sparse pseudo-random graphs are Hamiltonian. J. Graph Theory, 42(1):17-33, 2003.
https://doi.org/10.1002/jgt.10065
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 A generalization of Bondy's pancyclicity theorem 5 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.
C. McDiarmid and N. Yolov. Hamilton cycles, minimum degree, and bipartite holes. Journal of Graph Theory, 86(3):277-285, 2017.
https://doi.org/10.1002/jgt.22114
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
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
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Nemanja Draganić, David Munha Correia, Benny Sudakov