2023/06/21 by Letzter, Shoham · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2306.12579
A well-known result due to Chvatál and Erdős (1972) asserts that, if a graph G satisfies κ(G) ≥ α(G), where κ(G) is the vertex-connectivity of G, then G has a Hamilton cycle. We prove a similar result implying that a graph G is pancyclic, namely it contains cycles of all lengths between 3 and |G|: if |G| is large and κ(G) > α(G), then G is pancyclic. This confirms a conjecture of Jackson and Ordaz (1990) for large graphs, and improves upon a very recent result of Draganić, Munhá-Correia, and Sudakov.