Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423836 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
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
Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou,