Linear Colorings of Subcubic Graphs

ACO Student Seminar
Friday, September 14, 2012 - 14:00
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech, Math
A linear coloring of a graph is a proper coloring of the vertices of the graph so that each pair of color classes induce a union of disjoint paths.  In this talk, I will prove that for every connected graph with maximum degree at most three and every assignment of lists of size four to the vertices of the graph, there exists a linear coloring such that the color of each vertex belongs to the list assigned to that vertex and the neighbors of every degree-two vertex receive different colors, unless the graph is $C_5$ or $K_{3,3}$.   This confirms a conjecture raised by Esperet, Montassier, and Raspaud. Our proof is constructive and yields a linear-time algorithm to find such a coloring. This is joint work with Gexin Yu.