Linear colorings of subcubic graphs

Abstract

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 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 $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.

Cited by in corpus (6)

• Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
• Size of the Largest Induced Forest in Subcubic Graphs of Girth at least Four and Five
• Proper Conflict-free Coloring of Graphs with Large Maximum Degree
• An upper bound on the fractional chromatic number of triangle-free subcubic graphs
• Asymptotically Optimal Proper Conflict-Free Colouring
• Relaxation of Wegner's Planar Graph Conjecture for maximum degree 4