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

preprint2014arXivOpen access

Abstract

For a prime power qq, let ERqER_q denote the Erdős-Rényi orthogonal polarity graph. We prove that if qq is an even power of an odd prime, then χ(ERq)≤2q+O(q/log⁡q)χ( 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 qq is an odd power of an odd prime and satisfies some condition on irreducible polynomials, then we improve the best known upper bound for χ(ERq)χ(ER_{q}) substantially. We also show that for sufficiently large qq, every ERqER_q contains a subgraph that is not 3-chromatic and has at most 36 vertices.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.