Advertisement
Published in:
2020 | OriginalPaper | Chapter
The List 2-Distance Coloring of Sparse Graphs
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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)\).