Geodesic
On the chromatic number of the Erdős-Rényi orthogonal polarity graph
Xing Peng1 ; Michael Tait1 ; Craig Timmons2
1University of California San Diego
2California State University Sacramento
The electronic journal of combinatorics, Tome 22 (2015) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

For a prime power $q$, let $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 ( 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.
DOI : 10.37236/4893
Classification : 05C15, 05C35
Mots-clés : orthogonal polarity graphs, Turán number, forbidden subgraph, chromatic number

Xing Peng  1   ; Michael Tait  1   ; Craig Timmons  2

1 University of California San Diego
2 California State University Sacramento 
@article{10_37236_4893,
     author = {Xing Peng and Michael Tait and Craig Timmons},
     title = {On the chromatic number of the {Erd\H{o}s-R\'enyi} orthogonal polarity graph},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {2},
     doi = {10.37236/4893},
     zbl = {1312.05053},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4893/}
}
TY  - JOUR
AU  - Xing Peng
AU  - Michael Tait
AU  - Craig Timmons
TI  - On the chromatic number of the Erdős-Rényi orthogonal polarity graph
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4893/
DO  - 10.37236/4893
ID  - 10_37236_4893
ER  - 
%0 Journal Article
%A Xing Peng
%A Michael Tait
%A Craig Timmons
%T On the chromatic number of the Erdős-Rényi orthogonal polarity graph
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/4893/
%R 10.37236/4893
%F 10_37236_4893
Xing Peng; Michael Tait; Craig Timmons. On the chromatic number of the Erdős-Rényi orthogonal polarity graph. The electronic journal of combinatorics, Tome 22 (2015) no. 2. doi: 10.37236/4893

Cité par Sources :