Coloring with defect

Abstract

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.