# Cycles in Graphs of Large Chromatic Number

 Importance: Medium ✭✭
 Author(s): Brewster, Richard C. McGuinness, Sean Moore, Benjamin Noel, Jonathan A.
 Subject: Graph Theory » Coloring » » Vertex coloring
 Keywords: chromatic number cycles
 Posted by: Jon Noel on: September 20th, 2015
Conjecture   If , then contains at least cycles of length .

Chudnovsky, Plumettaz, Scott and Seymour [CPSS] proved that every graph with chromatic number at least contains a cycle of length . A simpler proof was found by Wrochna [W]. Wrochna's argument was generalised by Brewster, McGuinness, Moore and Noel [BMMN] to the following: if , then contains at least TeX Embedding failed! cycles of length .} The compete graph on vertices has exactly cycles of length and so the conjecture above, if true, would be best possible.

## Bibliography

[BMMN] R. C. Brewster, S. McGuinness, B. Moore, J. A. Noel, A Dichotomy Theorem for Circular Colouring Reconfiguration, submitted, arXiv:1508.05573v1.

[CPSS] M. Chudnovsky, M. Plumettaz, A. Scott, and P. Seymour, The Structure of Graphs with no Cycles of Length Divisible by Three, in preparation.

[Wro] M. Wrochna, unpublished.

* indicates original appearance(s) of problem.