Article ID Journal Published Year Pages File Type
4949757 Discrete Applied Mathematics 2017 11 Pages PDF
Abstract
A vertex coloring is called 2-distance if any two vertices at distance at most 2 from each other get different colors. Let χ2(G) be the 2-distance chromatic number of a graph G. Suppose G is a plane graph with girth 5 and maximum degree Δ. In this paper, we prove that if Δ∉{7,8}, then χ2(G)≤Δ+7. Furthermore, we show that χ2(G)≤Δ+4 if Δ is sufficiently large.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,