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.
