Article ID Journal Published Year Pages File Type
6423836 Electronic Notes in Discrete Mathematics 2011 6 Pages PDF
Abstract

A 2-distance coloring of a graph is a coloring of the vertices such that two vertices at distance at most 2 receive distinct colors. We prove that every graph with maximum degree Δ at least 4 and maximum average degree less that 73 admits a 2-distance (Δ+1)-coloring. This result is tight. This improves previous known results of Dolama and Sopena.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,