On the chromatic number of the Erdős-Rényi orthogonal polarity graph (Q2344823)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the chromatic number of the Erdős-Rényi orthogonal polarity graph |
scientific article |
Statements
On the chromatic number of the Erdős-Rényi orthogonal polarity graph (English)
0 references
18 May 2015
0 references
Summary: For a prime power \(q\), let \(\mathrm{ER}_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 (\mathrm{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(\mathrm{ER}_{q})\) substantially. We also show that for sufficiently large \(q\), every \(\mathrm{ER}_q\) contains a subgraph that is not 3-chromatic and has at most 36 vertices.
0 references
orthogonal polarity graphs
0 references
Turán number
0 references
forbidden subgraph
0 references
chromatic number
0 references