### Linear Colorings of Subcubic Graphs

- Series
- ACO Student Seminar
- Time
- Friday, September 14, 2012 - 14:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Chun-Hung Liu – 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.