A celebrated meta-conjecture of \textit{J. A. Bondy} [Colloq. Math. Soc. Janos Bolyai 10, 181--188 (1975; Zbl 0324.05115)] states that every non-trivial condition implying Hamiltonicity also implies pancyclicity (up to possibly a few exceptional graphs). The authors show that every graph \(G\) with \(\kappa(G) > (1+o(1))\alpha(G)\) is pancyclic, where \(\alpha(G)\) is the independence number and \(\kappa(G)\) the connectivity of \(G\). This extends the famous Chvátal-Erdős condition for Hamiltonicity and proves asymptotically a 30-year-old conjecture of \textit{B. Jackson} and \textit{O. Ordaz} [Discrete Math. 84, No. 3, 241--254 (1990; Zbl 0726.05043)]. An open problem concludes the paper.
- A cycle structure theorem for Hamiltonian graphs
- A note on Hamiltonian circuits
- A solution to Erdős and Hajnal’s odd cycle problem
- Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
- Chvátal–Erdős Theorem: Old Theorem with New Aspects
- Counting Hamilton decompositions of oriented graphs
- Cycle lengths and minimum degree of graphs
- Cycle lengths in expanding graphs
- Cycle lengths in sparse random graphs
- Cycle spectra of Hamiltonian graphs
- Cycles of even length in graphs
- Divisible subdivisions
- Extremal problems for cycles in graphs
- Hamilton cycles in graphs and hypergraphs: an extremal perspective
- Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
- Hamiltonian circuits in random graphs
- Hamiltonian cycles in Dirac graphs
- Hamiltonian degree conditions which imply a graph is pancyclic
- scientific article; zbMATH DE number 3922707 (Why is no real title available?)
- scientific article; zbMATH DE number 3465354 (Why is no real title available?)
- New sufficient conditions for cycles in graphs
- On cycle—Complete graph ramsey numbers
- On Hamilton's ideals
- Pancyclic graphs. I
- Pancyclicity of Hamiltonian and highly connected graphs
- Pancyclism in Chvátal-Erdős' graphs
- Proof of the 1-factorization and Hamilton Decomposition Conjectures
- Recent advances on the Hamiltonian problem: survey III
- Robust Hamiltonicity of Dirac graphs
- Some Theorems on Abstract Graphs
- The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
This page was built for publication: Chvátal-Erdős condition for pancyclicity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6601490)
