Graphs with Four Independent Crossings Are Five Colorable
Nathan Reid Harman · Rose-Hulman Scholar (Rose–Hulman Institute of Technology) · 2008
Albertson conjectured that if a graph can be drawn in the plane in such a way that any two crossings are independent, then the graph can be 5-colored. He proved it for up to three independent crossings. We prove this for four crossings by showing that any such graph has an independent set of size 4 with one vertex in each crossing, and give an example to show that this method fails for five independent crossings.