Geodesic
Crossings, colorings, and cliques
The electronic journal of combinatorics, Tome 16 (2009) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Albertson conjectured that if graph $G$ has chromatic number $r$, then the crossing number of $G$ is at least that of the complete graph $K_r$. This conjecture in the case $r=5$ is equivalent to the four color theorem. It was verified for $r=6$ by Oporowski and Zhao. In this paper, we prove the conjecture for $7 \leq r \leq 12$ using results of Dirac; Gallai; and Kostochka and Stiebitz that give lower bounds on the number of edges in critical graphs, together with lower bounds by Pach et al. on the crossing number of graphs in terms of the number of edges and vertices.
DOI : 10.37236/134
Classification : 05C10, 05C15 
@article{10_37236_134,
     author = {Michael O. Albertson and Daniel W. Cranston and Jacob Fox},
     title = {Crossings, colorings, and cliques},
     journal = {The electronic journal of combinatorics},
     year = {2009},
     volume = {16},
     number = {1},
     doi = {10.37236/134},
     zbl = {1182.05035},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/134/}
}
TY  - JOUR
AU  - Michael O. Albertson
AU  - Daniel W. Cranston
AU  - Jacob Fox
TI  - Crossings, colorings, and cliques
JO  - The electronic journal of combinatorics
PY  - 2009
VL  - 16
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/134/
DO  - 10.37236/134
ID  - 10_37236_134
ER  - 
%0 Journal Article
%A Michael O. Albertson
%A Daniel W. Cranston
%A Jacob Fox
%T Crossings, colorings, and cliques
%J The electronic journal of combinatorics
%D 2009
%V 16
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/134/
%R 10.37236/134
%F 10_37236_134
Michael O. Albertson; Daniel W. Cranston; Jacob Fox. Crossings, colorings, and cliques. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/134

Cité par Sources :