Colorability, Frequency and Graffiti – \(119\)

Conjecture 119 in the file “Written on the Wall”, which contains the output of the computer program “Graffiti” of Fajtlowicz, states: If \(G\) has girth \(5\) then its chromatic number is not more than the maximum frequency of occurrence of a degree in \(G\). Our main result provides an affirmative solution to this conjecture if \(|G| = n\) is sufficiently large. We prove:
Theorem. Let \(k \geq 2\) be a positive integer and let \(G\) be a \(C_{2k}\)-free graph (containing no cycle of length \(2k\)).

1. There exists a constant \(c(k)\), depending only on \(k\),
   such that \(\chi(G) \leq c(k)^{k-1} \sqrt{f(G)}/\log |G|\),
   where \(f(G)\) is the frequency of the mode of the degree sequence of \(G\).
2. There exists a constant \(c(k)\), depending only on \(k\),
   such that \(\chi(G) \leq c(k)|G|^{1/k}/\log |G|\).
3. If girth \((G) \geq 5\) then \(\chi(G) \leq f(G)\) if \(|G| \geq e^{49}\).