On the chromatic number of the Erdős-Rényi orthogonal polarity graph

Abstract

For a prime power $q$, let $E{R}_q$ denote the Erdős-Rényi orthogonal polarity graph. We prove that if $q$ is an even power of an odd prime, then $\chi (E{R}_q)\le 2\sqrt{q}+O(\sqrt{q}/\log q)$. This upper bound is best possible up to a constant factor of at most 2. If $q$ is an odd power of an odd prime and satisfies some condition on irreducible polynomials, then we improve the best known upper bound for $\chi (E{R}_q)$ substantially. We also show that for sufficiently large $q$, every $E{R}_q$ contains a subgraph that is not 3-chromatic and has at most 36 vertices.

minor changes in the theorem for odd power case