This paper is concerned with algorithms and complexity results for defective
coloring, where a defective (k,d)-coloring is a k coloring of the vertices
of a graph such that each vertex is adjacent to at most d-self-colored
neighbors. First, (2,d) coloring is shown NP-complete for d >= 1, even
for planar graphs, and (3,1) coloring is also shown NP-complete for planar
graphs (while there exists a quadratic algorithm to (3,2)-color any planar
graph). A reduction from ordinary vertex coloring then shows (X,d) coloring
NP-complete for any X >= 3, d >= 0, as well as hardness of approximation
results.
Second, a generalization of Delta + 1 coloring defects is explored for graphs
of maximum degree Delta. Based on a theorem of Lovasz, we obtain an O(Delta E)
algorithm to (k, \1floor (Delta/k \rfloor) color any graph; this yields an
O(E) algorithm to (2,1)-color 3-regular graphs, and (3,2)-color 6-regular
graphs.
The generalization of Delta + 1 coloring is used in turn to generalize the
polynomial-time approximate 3- and k-coloring algorithms of Widgerson and
Karger-Motwani-Sudan to allow defects. For approximate 3-coloring, we
obtain an O(Delta E) time algorithm to $(\lceil({8n \over d})^{.5}\rceil,d)$
color, and a polynomial time algorithm to $(O((\frac{n} {d})^{.387}), d)$
color any 3-colorable graph.
DIMACS Home Page