Georgia Institute of Technology College of Sciences

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.