© 2004 by British Computer Society
Approximations for 
-Colorings of Graphs
1 Institute of Information and Computing Sciences, Utrecht University, Padualaan 14, 3584 CH Utrecht, The Netherlands 2 Department of Mathematics and Computer Science, Vrije Universiteit, 1081 HV Amsterdam, The Netherlands 3 Department of Computer Science, University of Sciences & Arts of Oklahoma, Chickasha, OK 73018, USA
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.
Received 17 January 2002. Revised 11 June 2003.
Email: 
Email: