Pith. sign in

REVIEW

A strengthening on odd cycles in graphs of given chromatic number

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2012.10624 v2 pith:RGFQHROX submitted 2020-12-19 math.CO

classification math.CO
keywords cycleschromaticcontainslengthsnumberconjectureconsecutiveevery
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

Resolving a conjecture of Bollob\'{a}s and Erd\H{o}s, Gy\'{a}rf\'{a}s proved that every graph $G$ of chromatic number $k+1\geq 3$ contains cycles of $\lfloor\frac{k}{2}\rfloor$ distinct odd lengths. We strengthen this prominent result by showing that such $G$ contains cycles of $\lfloor\frac{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\geq 7$ contains $k$ cycles of consecutive lengths, except that some block is $K_{k+1}$. As corollaries, this confirms a conjecture of Verstra\"ete and answers a question of Moore and West.

Discussion (0). Continue with ORCID to comment.

Pith tools