School Seminars and Colloquia

Albertson's conjecture and 5-coloring non-planar graphs

Discrete Structures and Algorithms (Seminar)

by Janos Barat


Institution: Monash University
Date: Tue 8th November 2011
Time: 11:00 AM
Location: Russell Love Theatre, Richard Berry Building

Abstract: A graph is planar, if it can be drawn in the plane without edge crossings. It follows from the Euler-formula, that any planar graph has a vertex of degree at most 5. Therefore, using a greedy coloring algorithm, we can trivially color the vertices of a planar graph by 6 colors.
It is still easy to prove that 5 colors suffice. What happens if we allow some edge crossings in the drawing? Can we still 5 color the vertices? Is there any connection between the minimum number of crossings in a drawing of a graph G and its chromatic number? Both of these graph parameters are hard to compute. Still, Mike Albertson formulated a conjecture in 2007 that for any r-chromatic G, the crossing number of G is at least the crossing number of $K_r$, the complete graph on $r$ vertices. This conjecture is a weakening of Hajos conjecture, and it includes the 4 color theorem as a subcase. We will show that this conjecture follows from some known results up to a factor of 4. It is also true for r at most 16, despite the fact that we only know the crossing number of $K_r$ for $r$ at most 12.