ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


M. Chen, Y. Li, L. Zhang


Linear list coloring of some sparse graph


Discussiones Mathematicae Graph Theory

Received: 2017-05-12, Revised: 2018-01-31, Accepted: 2018-07-31,


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 \in V (G)\}$ such that $c(v) \in L(v)$ for all $v\in V (G)$, and $G$ is linearly $k$-choosable if $G$ is linearly $L$-colorable for any list assignment with $|L(v)|\ge 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)\ge \left\lceil \frac{\Delta(G)}{2}\right\rceil+1$ for any graph $G$ with maximum degree $\Delta(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 $\Delta(G)\ge 7$, then $lc_l(G)= \left\lceil \frac{\Delta(G)}{2}\right\rceil+1$; (2) if $mad(G)<\frac{18}{7}$ and $\Delta(G)\ge 5$, then $lc_l(G)=\left\lceil \frac{\Delta(G)}{2}\right\rceil+1$; (3) if $mad(G)<\frac{20}{7}$ and $\Delta(G)\ge5$, then $lc_l(G)\le\left\lceil \frac{\Delta(G)}{2}\right\rceil+2$.


linear coloring, maximum average degree, planar graphs, discharging