The Shortest Odd Cycle Is Chordless

A chord of an odd cycle splits it into two cycles, exactly one of which is odd, and both of which are shorter. A shortest odd cycle therefore carries no chord, and the subgraph it induces is exactly itself. Its chromatic number is $3$, whatever the chromatic number of the ambient graph. This is the precise sense in which chromatic number fails to localise to odd cycles: a graph of chromatic number $10^6$ still contains an odd cycle spanning a subgraph of chromatic number $3$, and the witness is available at the shortest one. Girth is a separate and weaker instrument. A chorded cycle has length at least $2g - 2$, so girth forbids chords only below that threshold, and the threshold is attained.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-09-21
DOI
https://doi.org/10.5281/zenodo.22883463
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
preprint

The Shortest Odd Cycle Is Chordless

Christopher Mills
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

The Shortest Odd Cycle Is Chordless

Christopher Mills
preprint en

Abstract

A chord of an odd cycle splits it into two cycles, exactly one of which is odd, and both of which are shorter. A shortest odd cycle therefore carries no chord, and the subgraph it induces is exactly itself. Its chromatic number is $3$, whatever the chromatic number of the ambient graph. This is the precise sense in which chromatic number fails to localise to odd cycles: a graph of chromatic number $10^6$ still contains an odd cycle spanning a subgraph of chromatic number $3$, and the witness is available at the shortest one. Girth is a separate and weaker instrument. A chorded cycle has length at least $2g - 2$, so girth forbids chords only below that threshold, and the threshold is attained.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

The Shortest Odd Cycle Is Chordless — Christopher Mills · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS