Article ID Journal Published Year Pages File Type
4649900 Discrete Mathematics 2009 4 Pages PDF
Abstract

We generalize the Five-Color Theorem by showing that it extends to graphs with two crossings. Furthermore, we show that if a graph has three crossings, but does not contain K6K6 as a subgraph, then it is also 5-colorable. We also consider the question of whether the result can be extended to graphs with more crossings.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,