Colorability, Frequency and Graffiti – $119$

Abstract

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\ge 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)\le 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)\le c(k)|G{|}^{1/k}/\log |G|$.
3. If girth $(G)\ge 5$ then $\chi (G)\le f(G)$ if $|G|\ge e^{49}$.