On the chromatic number of the Erdős-Rényi orthogonal polarity graph (Q2344823): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Import240304020342 (talk | contribs)
Set profile property.
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank

Revision as of 06:47, 5 March 2024

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
    0 references
    0 references
    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

    Identifiers