Linear List Coloring of Some Sparse Graphs

Chen, Ming ; Li, Yusheng ; Zhang, Li 

Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 51-64

Résumé

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 lc_l(G). It is clear that lc_l(G)≥⌈Δ(G)/1⌉+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) lt;8/3 and Δ(G) ≥ 7, then lc_l(G)=⌈Δ(G)/2⌉+1; (2) if mad(G) lt;187 and Δ(G) ≥ 5, then lc_l(G)=⌈Δ(G)/2⌉+1; (3) if mad(G) lt;207 and Δ(G) ≥ 5, then lc_l(G)≤⌈Δ(G)/2⌉+2.

Détail

Keywords: linear coloring, maximum average degree, planar graphs, discharging