Graphs with Four Independent Crossings Are Five Colorable

Authors

Nathan Harman, University of Massachusetts AmherstFollow

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.

Author Bio

I am currently a freshman math major at University of Massachusetts Amherst. Howeverthis work was completed during the summer before my entrance here. As far as otherbiographical information, I graduated from Rolling Meadows high school in RollingMeadows Illinois this June. During high school I competed in math team, both for myschool and for the Chicago ARML team, and I spent two of my summers at theHampshire College Summer Studies in Mathematics. When I am not doing math I enjoyplaying videogames, playing competitive dodgeball, and eating cheese.

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 12.
Available at: https://scholar.rose-hulman.edu/rhumj/vol9/iss2/12