Linear colorings of subcubic graphs
From MaRDI portal
Publication:2444734
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 or . 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.
Recommendations
- Linear coloring of graphs
- scientific article; zbMATH DE number 2089961
- COLORING ALGORITHMS ON SUBCUBIC GRAPHS
- Acyclic colorings of subcubic graphs
- Linear coloring of sparse graphs
- Total colouring of new classes of subcubic graphs
- Acyclic edge coloring of subcubic graphs
- The linear \(t\)-colorings of Sierpiński-like graphs
- A concise proof for total coloring subcubic graphs
- Colorings of complements of line graphs
Cites work
- -list vertex coloring in linear time
- Acyclic colorings of planar graphs
- Acyclic colorings of subcubic graphs
- Acyclic edge coloring of subcubic graphs
- Colouring a graph frugally
- scientific article; zbMATH DE number 3735847 (Why is no real title available?)
- scientific article; zbMATH DE number 821271 (Why is no real title available?)
- Improved bounds on linear coloring of plane graphs
- Linear and 2-frugal choosability of graphs of small maximum average degree
- Linear choosability of graphs
- Linear choosability of sparse graphs
- Linear coloring of graphs
- Linear coloring of planar graphs with large girth
- Linear coloring of sparse graphs
- List-Coloring Squares of Sparse Subcubic Graphs
- List-coloring the square of a subcubic graph
- On arc-coloring of subcubic graphs
- On list edge-colorings of subcubic graphs
- Upper bounds on the linear chromatic number of a graph
Cited in
(18)- Remarks on proper conflict-free colorings of graphs
- Linear list coloring of some sparse graphs
- Coloring of pseudocubic graphs in three colors
- Linear colorings of simplicial complexes and collapsing
- Δ-List Vertex Coloring in Linear Time
- Linear choosability of graphs
- Linear coloring of sparse graphs
- scientific article; zbMATH DE number 2089961 (Why is no real title available?)
- Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
- Relaxation of Wegner's planar graph conjecture for maximum degree 4
- Brooks-type theorems for relaxations of square colorings
- Proper conflict-free coloring of graphs with large maximum degree
- Remarks on proper conflict-free degree-choosability of graphs with prescribed degeneracy
- Proper conflict-free degree-choosability of outerplanar graphs
- Asymptotically optimal proper conflict-free coloring
- Results on proper conflict-free list coloring of graphs
- -list vertex coloring in linear time
- Linear choosability of graphs
This page was built for publication: Linear colorings of subcubic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2444734)
