Abstract
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.
Faculty Sponsor
Michael J. Pelsmajer
Recommended Citation
Harman, Nathan
(2008)
"Graphs with Four Independent Crossings Are Five Colorable,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 9:
Iss.
2, Article 15.
Available at:
https://scholar.rose-hulman.edu/rhumj/vol9/iss2/15