Thickness of graphs « Ben Braun’s Mathematics Weblog

Thickness of graphs

August 13, 2008 · Leave a Comment

Here is an interesting problem I heard about during a talk by Ellen Gethner. Given a graph $G$ , the thickness of $G$ is the least size of a collection of planar graphs on the vertices of $G$ such that $G$ is the union of these planar graphs. This is related to things like layering electrical circuits on a chip with multiple layers. The thickness is an interesting invariant. In particular, the following question exists: What is the maximal chromatic number of a graph of thickness $t$ ? For each $t\geq 3$ , this value is known to be one of $6t,6t-1,6t-2$ , though which of these is the correct answer for each $t$ is still unknown. For $t=2$ , this value is one of $9,10,11,12$ . For $t=1$ , this is the celebrated four-color theorem for planar graphs. A recent paper by Gethner and others in the Journal of Graph Theory (a preprint is available on Gethner’s website) provides an infinite family of chromatic number $9$ graphs with thickness $2$ . I think this is a beautiful problem and worthy of more attention.