2020 | OriginalPaper | Buchkapitel
The List 2-Distance Coloring of Sparse Graphs
Erschienen in:
Data Science
Abstract
The k-2-distance coloring of a graph G is a mapping \(c:V(G)\rightarrow \{1,2,\cdots ,k\}\) such that for every pair of \(u,v\in V(G)\) satisfying \(0<d_{G}(u,v)\le 2\), \(c(u)\ne c(v)\). A graph G is list 2-distance k-colorable if any list L of admissible colors on V(G) of size k allows a 2-distance coloring \(\varphi \) such that \(\varphi (v)\in L(v)\). The least k for which G is list 2-distance k-colorable is denoted by \(\chi _{2}^{l}(G)\). In this paper, we proved that if a graph G with the maximum average degree \(mad(G)<2+\frac{9}{10}\) and \(\bigtriangleup (G)=6\), then \(\chi _{2}^{l}(G)\le 12\); if a graph G with \(mad(G)<2+\frac{4}{5}(\mathrm {resp.} mad(G)<2+\frac{17}{20})\) and \(\bigtriangleup (G)=7\), then \(\chi _{2}^{l}(G)\le 11(\mathrm {resp.} \chi _{2}^{l}(G)\le 12)\).
