Geodesic
Linear List Coloring of Some Sparse Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 51-64.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: linear coloring, maximum average degree, planar graphs, discharging 
@article{DMGT_2021_41_1_a2,
     author = {Chen, Ming and Li, Yusheng and Zhang, Li},
     title = {Linear {List} {Coloring} of {Some} {Sparse} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {51--64},
     publisher = {mathdoc},
     volume = {41},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a2/}
}
TY  - JOUR
AU  - Chen, Ming
AU  - Li, Yusheng
AU  - Zhang, Li
TI  - Linear List Coloring of Some Sparse Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 51
EP  - 64
VL  - 41
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a2/
LA  - en
ID  - DMGT_2021_41_1_a2
ER  - 
%0 Journal Article
%A Chen, Ming
%A Li, Yusheng
%A Zhang, Li
%T Linear List Coloring of Some Sparse Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 51-64
%V 41
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a2/
%G en
%F DMGT_2021_41_1_a2
Chen, Ming; Li, Yusheng; Zhang, Li. Linear List Coloring of Some Sparse Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 51-64. http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a2/

[1] D.W. Cranston and G. Yu, Linear choosability of sparse graphs, Discrete Math. 311 (2011) 1910–1917. doi: 10.1016/j.disc.2011.05.017

[2] W. Dong, B. Xu and X. Zhang, Improved bounds on linear coloring of plane graphs, Sci. China Math. 53 (2010) 1895–1902. doi: 10.1007/s11425-010-3073-0

[3] W. Dong and W. Lin, On linear coloring of planar graphs with small girth, Discrete Appl. Math. 173 (2014) 35–44. doi: 10.1016/j.dam.2014.03.019

[4] L. Esperet, M. Montassier and A. Raspaud, Linear choosability of graphs, Discrete Math. 308 (2008) 3938–3950. doi: 10.1016/j.disc.2007.07.112

[5] C. Li, W. Wang and A. Raspaud, Upper bounds on the linear chromatic number of a graph, Discrete Math. 311 (2011) 232–238. doi: 10.1016/j.disc.2010.10.023

[6] C.H. Liu and G. Yu, Linear colorings of subcubic graphs, European J. Combin. 34 (2013) 1040–1050. doi: 10.1016/j.ejc.2013.02.008

[7] Y. Wang and Q. Wu, Linear coloring of sparse graphs, Discrete Appl. Math. 160 (2012) 664–672. doi: 10.1016/j.dam.2011.10.028

[8] R. Yuster, Linear coloring of graphs, Discrete Math. 185 (1998) 293–297. doi: 10.1016/S0012-365X(97)00209-4