Authors:
M. Chen, Y. Li, L. Zhang
Title:
Linear list coloring of some sparse graph
Source:
Discussiones Mathematicae Graph Theory
Received 12.05.2017, Revised 31.01.2018, Accepted 31.07.2018, doi: 10.7151/dmgt.2169

Abstract:
A linear k-coloring of a graph is a proper k-coloring of the graph such that any subgraph induced by the vertices of any pair of color classes is a union of vertex-disjoint paths. A graph G is linearly L-colorable if there is a linear coloring c of G for a given list assignment L={L(v): v ∈V (G)} such that c(v) ∈L(v) for all v∈V (G), and G is linearly k-choosable if G is linearly L-colorable for any list assignment with |L(v)|≥ k. The smallest integer k such that G is linearly k-choosable is called the linear list chromatic number, denoted by lcl(G). It is clear that lcl(G)≥ \left⌈ \frac{Δ(G)}{2}\right⌉+1 for any graph G with maximum degree Δ(G). The maximum average degree of a graph G, denoted by mad(G), is the maximum of the average degrees of all subgraphs of G. In this note, we shall prove {the following.} Let G be a graph, (1) if mad(G)<\frac{8}{3} and Δ(G)≥ 7, then lcl(G)= \left⌈ \frac{Δ(G)}{2}\right⌉+1; (2) if mad(G)<\frac{18}{7} and Δ(G)≥ 5, then lcl(G)=\left⌈ \frac{Δ(G)}{2}\right⌉+1; (3) if mad(G)<\frac{20}{7} and Δ(G)≥5, then lcl(G)\le\left⌈ \frac{Δ(G)}{2}\right⌉+2.
Keywords:
linear coloring, maximum average degree, planar graphs, discharging

Links:
PDF