arXiv:1006.3783 [math.CO]AbstractReferencesReviewsResources
Crossings, colorings, and cliques
Michael O. Albertson, Daniel W. Cranston, Jacob Fox
Published 2010-06-18Version 1
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.
Comments: 15 pages
Journal: Electronic J. of Combinatorics, R45 16(1), 2009
Categories: math.CO
Subjects: 05C10
Tags: journal article
Related articles: Most relevant | Search more
arXiv:1309.6930 [math.CO] (Published 2013-09-24)
The Four Color Theorem and Trees
arXiv:2401.12222 [math.CO] (Published 2024-01-23)
A sequel to the adventure of RGB-tilings to explore the Four Color Theorem
arXiv:2309.09998 [math.CO] (Published 2023-09-17)
A renewal approach to prove the Four Color Theorem unplugged, Part III: Diamond routes, canal lines and $Σ$-adjustments