Searching for a Thickness-Two 10-Chromatic Graph and
Discovering Other Treasures Along The Way
Ellen Gethner
Department of Computer Science
 |
How many times have you run into a math, physics, computer science, astronomy, biology or other problem that starts with the word Find. For example find a three-legged bowtruckle. Or
find a Blast-Ended Screwt that is partial to Bertie Botts' Every Flavor Beans. Or find a non-abelian group of order four. Or find a simple undirected planar graph on 10 vertices with at least 35 edges. Or find six distinct Platonic Solids. Or find a galaxy that is 13 billion years old. Get the idea? I suppose you could Google your way to most any answer, but not for the following problem:
Find a 10-chromatic thickness-two graph.
Might an absent-minded professor have the answer buried in some long forgotten sheaf of notes? Or perhaps the elusive graph is tucked away in a file on a physicist's computer. Maybe the graph in question can be found in the night sky by a graph-theorist astronomer. Just what does the word Find mean for the problem at hand?
For the graph theory aficionados, here is more formal statement of the problem.
Abstract
A graph G is said to have thickness-t if the edges of G can be partitioned into t and no fewer planar graphs. For example, if G is planar, then G has
thickness-one. For another example, with the help of Kuratowski's Theorem, it is easy to see that K5 has thickness at least two. Exercise: Show that K5 has thickness exactly two.
A longstanding open problem is the following:
What is the largest chromatic number of any thickness-two graph?
The largest chromatic number of any thickness-two graph is known to be one of 9, 10, 11, or 12. The 9 is due to exactly one published example of a 9-critical thickness-two graph found by Thom Sulanke in 1973 and was reported by Martin Gardner in 1980. The 12 is due to a straightforward argument that relies on Euler's Formula for planar graphs.
We introduce a catalogue of new small 9-critical thickness-two graphs, and a construction that generates infinitely many 9-critical thickness-two graphs, thus providing ballast to the 9, and providing a stepping stone to the search for a 10-chromatic thickness-two graph as well. In addition new families of thickness-two graphs will be defined, some of which have a known asymptotically sharp upper bound for the chromatic number.
The (re)search for the thickness-two 10-chromatic graph treasure hunt has many connections with the Smith College Math Department both past and present, and I will highlight those connections throughout the talk.
