A strengthening on odd cycles in graphs of given chromatic number

2020/12/19 by Jun Gao, Gao, Jun, Qingyi Huo +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2012.10624

openalex publication_date 2020/12/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Resolving a conjecture of Bollobás and Erdős, Gyárfás proved that every graph G of chromatic number k+1≥ 3 contains cycles of \lfloor(k)/(2)\rfloor distinct odd lengths. We strengthen this prominent result by showing that such G contains cycles of \lfloor(k)/(2)\rfloor consecutive odd lengths. Along the way, combining extremal and structural tools, we prove a stronger statement that every graph of chromatic number k+1≥ 7 contains k cycles of consecutive lengths, except that some block is K_k+1. As corollaries, this confirms a conjecture of Verstraëte and answers a question of Moore and West.

Cited by

• Cycle lengths in graphs of given minimum degree
• Cycles of consecutive lengths in 3-connected graphs

Related

• A solution to Erdős and Hajnal's odd cycle problem
• Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
• Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyarfas' conjectures
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Induced subgraphs of graphs with large chromatic number. III. Long holes