# The smallest order of a 4-chromatic graph of given girth

Let $n_4(g)$ denote the smallest order of a $4$-chromatic graph with girth $g$. It is known that $n_4(4)=11$ [2] and $n_4(5)=21$ [1]. By a famous proof of Erdös, it is known that $n_4(g)$ is well-defined for all $g\geq 3$, and there have been subsequent explicit constructions, starting with one of Lovasz [3].

Question: What is the best known upper bound for $n_4(g)$?

Partial answers: In [4] is given a construction of Ramanujan graphs with the following properties. Let $p$ and $q$ be two distinct prime numbers both congruent to $1$ modulo $4$ such that $q$ is a quadratic residue modulo $p$. Then, there is a graph $X_{p,q}$ of order $\frac{q(q^2-1)}{2}$, chromatic number at least $\frac{p+1}{2\sqrt{p}}$, and girth at least $\frac{2\ln q}{\ln p}$. If $p\geq 62$, we have $\frac{p+1}{2\sqrt{p}}\geq 4$. So, $p=73$ is the smallest value of $p$ that would work for my question, so we can fix $p=73$ and obtain an infinite sequence of values of $q$ satisfying the above conditions, see [5]. We obtain roughly $n_4(g)\leq \frac{73^{3g/2}}{2}$ for infinitely many values of the girth $g$. I don't know if this construction is the smallest known one.

Edit (May 18, 2018) It is shown in [6] that $26\leq n_4(6)\leq 66$ and $30\leq n_4(7)\leq 171$. Moreover, generally $n_4(g)\geq 3\cdot 2^{(g-1)/2}-2$ for odd $g$ and $n_4(g)\geq 2\cdot 2^{g/2}-2$ for even $g$ [6].

• Were you interested in a similar question for an odd girth, there are quadratic bounds (both upper and lower). Aug 17, 2016 at 13:35
• Thanks, but I'm aware of this line of work. Actually the mentioned quadratic bounds raised my interest into asking this question! Aug 25, 2016 at 14:24
• You are completely right, thanks! That was nonsense, I removed it. This method gives a gigantic upper bound for $n_4(38)$! If we want, say, girth 7, with $p=73$ we'll need $q\geq exp(16)$. May 25, 2018 at 9:03