Approximations for -Colorings of Graphs
Hans L. Bodlaender · The Computer Journal · 2004
A λ-coloring of a graph G is an assignment of colors from the integer set {0,…,λ} to the vertices of the graph G such that vertices at distance of at most two get different colors and adjacent vertices get colors which are at least two apart. The problem of finding λ-colorings with optimal or near-optimal λ arises in the context of radio frequency assignment. We show that the problem of finding the minimum λ for planar graphs, bipartite graphs, chordal graphs and split graphs is NP-complete. We also give approximation algorithms for λ-coloring and compute upper bounds on the best possible λ for outerplanar graphs, graphs of treewidth k, permutation and split graphs. Except in the case of split graphs, all the above bounds for λ are linear in Δ, the maximum degree of the graph. For split graphs, we give a bound of ½Δ1.5 + 2Δ and we show that there are split graphs G with λ(G) = Ω(Δ1.5). Similar results are also given for variations of the λ-coloring problem.