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.
Michael J. Pelsmajer, Applied Mathematics, Illinois Institute of Technology firstname.lastname@example.org
"Graphs with Four Independent Crossings Are Five Colorable,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 9
, Article 15.
Available at: http://scholar.rose-hulman.edu/rhumj/vol9/iss2/15