Crossings, Colorings, and Cliques
Open Access
- 7 January 2009
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 16 (1) , R45
Abstract
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.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Coloring plane graphs with independent crossingsJournal of Graph Theory, 2009
- Coloring graphs with crossingsDiscrete Mathematics, 2009
- Improving the Crossing Lemma by Finding More Crossings in Sparse GraphsDiscrete & Computational Geometry, 2006
- A successful concept for measuring non-planarity of graphs: the crossing numberDiscrete Mathematics, 2004
- A new lower bound on the number of edges in colour-critical graphs and hypergraphsJournal of Combinatorial Theory, Series B, 2003
- On the minimal number of edges in color-critical graphsCombinatorica, 1997
- New lower bound techniques for VLSITheory of Computing Systems, 1984
- Crossing-Free Subgraphs1982
- The crossing number of K5,nJournal of Combinatorial Theory, 1970
- A Property of 4-Chromatic Graphs and some Remarks on Critical GraphsJournal of the London Mathematical Society, 1952