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

[1] Mathoverflow question: What is the smallest 4-chromatic graph of girth 5?
[2] V. Chvatal. The minimality of the Mycielski graph. Lecture Notes in Mathematics 406:243-246, 1974.
[3] L. Lovasz. On chromatic number of finite set systems. Acta Mathematica Academiae Scientarium Hungaricae 19(1-2):59-67, 1968.
[4] A. Lubotsky, R. Philips and P. Sarnak. Ramanujan graphs. Combinatorica 8(3):261-277, 1988.
[5] Answer to a Mathematics SE question: How to find pairs of primes satisfying certain properties? [6] G. Exoo and J. Goedgebeur. Bounds for the smallest $k$-chromatic graphs of given girth, preprint, 2018.

  • 1
    $\begingroup$ Were you interested in a similar question for an odd girth, there are quadratic bounds (both upper and lower). $\endgroup$ Aug 17, 2016 at 13:35
  • $\begingroup$ Thanks, but I'm aware of this line of work. Actually the mentioned quadratic bounds raised my interest into asking this question! $\endgroup$ Aug 25, 2016 at 14:24
  • $\begingroup$ 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)$. $\endgroup$ May 25, 2018 at 9:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.