201. 2-Distance coloring of planar graphs with maximum degree 5.
- Author
-
Chen, Ming, Jiang, Lu, Wang, Min, and Zhou, Shan
- Abstract
A 2-distance coloring of a graph is a proper k-coloring in which any two vertices with distance at most two get different colors. The 2-distance number is the smallest number k such that G has a 2-distance k-coloring, denoted as χ2(G). In 1977, Wegner conjectured that for each planar graph G with maximum degree Δ, χ2(G) ≤ 7 if Δ ≤ 3, χ2(G) ≤ Δ + 5 if 4 ≤ Δ ≤ 7, and χ2(G) ≤⌊3Δ 2 ⌋ + 1 if Δ ≥ 8. In 2001, Thomassen supported the conjecture by proving the case Δ = 3. The conjecture is still open even for Δ = 4. In this paper, we show that χ2(G) ≤ 17 for the case Δ ≤ 5 which improves the upper bound 18 recently obtained by Hou
et al. [ABSTRACT FROM AUTHOR]- Published
- 2024
- Full Text
- View/download PDF