Cycles in Graphs of Large Chromatic Number

Recomm. for undergrads: no
Posted by: Jon Noel
on: September 20th, 2015

\begin{conjecture} If $\chi(G)>k$, then $G$ contains at least $\frac{(k+1)(k-1)!}{2}$ cycles of length $0\bmod k$. \end{conjecture}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}

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: \emph{if $\chi(G)>k$, then $G$ contains at least $\frac{(k-1)!}{2}$ 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.


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

[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.