Home » Subject » Graph Theory » Coloring » Vertex coloring
Importance: Medium ✭✭
Author(s): Brewster, Richard C.
McGuinness, Sean
Moore, Benjamin
Noel, Jonathan A.
Subject: Graph Theory
» Coloring
» » Vertex coloring
Keywords: chromatic number
cycles
Recomm. for undergrads: no
Posted by: Jon Noel
on: September 20th, 2015
Conjecture   If $ \chi(G)>k $, then $ G $ contains at least $ \frac{(k+1)(k-1)!}{2} $ cycles of length $ 0\bmod k $.

Chudnovsky, Plumettaz, Scott and Seymour [CPSS] proved that every graph with chromatic number at least $ 4 $ contains a cycle of length $ 0\bmod 3 $. A simpler proof was found by Wrochna [W]. Wrochna's argument was generalised by Brewster, McGuinness, Moore and Noel [BMMN] to the following: if $ \chi(G)>k $, then $ G $ contains at least TeX Embedding failed! cycles of length $ 0\bmod k $.} The compete graph on $ k+1 $ vertices has exactly $ \frac{(k+1)(k-1)!}{2} $ cycles of length $ 0\bmod k $ and so the conjecture above, if true, would be best possible.

Related problems

Bounding the chromatic number of graphs with no odd hole

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.
add new comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options