Coloring graphs with crossings

2005/01/25 by Bogdan Oporowski, Oporowski, Bogdan, David Zhao +1
Mathematics · #05C15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15

paper · pdf · doi:10.48550/arxiv.math/0501427

5 pages

arxiv created 2005/01/25 · arxiv updated 2009/12/01

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 K₆ 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

• On a conjecture concerning 4-coloring of graphs with one crossing
• Coloring plane graphs with independent crossings
• 5-choosability of graphs with 2 crossings
• Graphs without a 3-connected subgraph are 4-colorable
• A formal proof of the four color theorem