On the complexity of distance-2 coloring
Errol L. Lloyd, Sharad Ramanathan · 2003
The authors study the problem of distance-2 colorings of the vertices of undirected graphs. In such a coloring, vertices separated by a distance of less than or equal to two must receive different colors. This problem has direct application to the problem of broadcast scheduling in multihop radio networks. The authors show that even when restricted to planar graphs, finding a minimum such coloring is NP-complete. They then describe a good (constant times optimal) approximation algorithm for the distance-2 coloring of planar graphs. They also extend this analysis of the algorithm to deal with general graphs. They show that the performance of the algorithm has a worst-case bound that is proportional to the product of the graph arboricity and the maximum vertex degree. Previous algorithms could only guarantee a bound proportional to the square of the maximum degree.>