Title: Crossings, Colorings, and Cliques
Speaker: Dan Cranston, Rutgers University
Date: Wednesday, April 8, 2009 12:00pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
There are three classical relaxations of planarity (which we define below): the genus of a graph, the thickness of a graph, and the crossing number of a graph. The {\it genus} of a graph is the minimum genus of a surface on which the graph can be embedded. The {\it thickness} of a graph is the minimum number of planar subgraphs needed to partition the edges of the graph. The {\it crossing number} of a graph is the minimum number of pairs of edges that cross in a drawing of G in the plane (the minimum is taken over all drawings).
The relationship between the genus of a graph and its chromatic number has been studied extensively. This study culminated in the late 1960s with the Ringle-Youngs Theorem, which states that the maximum chromatic number of a graph embeddable in each surface S is precisely the size of the largest clique embeddable in S. Similar results are known for thickness; they say that the maximum chromatic number of a graph with thickness k is at most 1 more than the size of the largest clique with thickness k. What is surprising, then, is how little is known about the relationship between chromatic number and crossing number. In 2007, Mike Albertson conjectured that if graph G has chromatic number r, then G has crossing number at least that of K_r. The case r = 5 is equivalent to the 4 Color Theorem and the only other case verified until now was r = 6. Recently Albertson, Jacob Fox, and I verified the conjecture for $7\le r \le 12$.