•  
  •  
 

Graphs with Four Independent Crossings Are Five Colorable

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.

This document is currently not available here.

Share

COinS