pith. sign in

arxiv: 1408.4065 · v2 · pith:L2Z3PNFVnew · submitted 2014-08-18 · 🧮 math.CO

On the chromatic number of the ErdH{o}s-R\'enyi orthogonal polarity graph

classification 🧮 math.CO
keywords powerprimebestboundchromaticenyigraphorthogonal
0
0 comments X
read the original abstract

For a prime power $q$, let $ER_q$ denote the Erd\H{o}s-R\'enyi orthogonal polarity graph. We prove that if $q$ is an even power of an odd prime, then $\chi ( ER_{q}) \leq 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(ER_{q})$ substantially. We also show that for sufficiently large $q$, every $ER_q$ contains a subgraph that is not 3-chromatic and has at most 36 vertices.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.