TY - JOUR

T1 - Linear colorings of subcubic graphs

AU - Liu, Chun Hung

AU - Yu, Gexin

N1 - Funding Information:
The second author’s research was supported in part by NSA grant H98230-12-1-0226 .

PY - 2013/8

Y1 - 2013/8

N2 - A linear coloring of a graph is a proper coloring of the vertices of the graph so that each pair of color classes induces a union of disjoint paths. In this paper, we 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 C5 or K3,3. This confirms a conjecture raised by Esperet, Montassier and Raspaud [L.Esperet, M.Montassier, and A. Raspaud, Linear choosability of graphs, Discrete Math. 308 (2008) 3938-3950]. Our proof is constructive and yields a linear-time algorithm to find such a coloring.

AB - A linear coloring of a graph is a proper coloring of the vertices of the graph so that each pair of color classes induces a union of disjoint paths. In this paper, we 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 C5 or K3,3. This confirms a conjecture raised by Esperet, Montassier and Raspaud [L.Esperet, M.Montassier, and A. Raspaud, Linear choosability of graphs, Discrete Math. 308 (2008) 3938-3950]. Our proof is constructive and yields a linear-time algorithm to find such a coloring.

UR - http://www.scopus.com/inward/record.url?scp=84875302824&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84875302824&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2013.02.008

DO - 10.1016/j.ejc.2013.02.008

M3 - Article

AN - SCOPUS:84875302824

SN - 0195-6698

VL - 34

SP - 1040

EP - 1050

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 6

ER -