Coloring with defect
Lenore Cowen, Wayne Goddard, C. Esther Jesurum · 1997
An (ordinary vertex) coloring is a partition of the vertices of a graph into independent sets. The chromatic number is the minimum number of colors needed to produce such a partition. This paper considers a relaxation of coloring in which the color classes partition the vertices into subgraphs of degree at most d. d is called the defect of the coloring. A graph which admits a vertex coloring into k color classes, where each vertex is adjacent to at most d self-colored neighbors is said to be (k; d) colorable. We consider defective coloring on graphs of bounded degree, bounded genus, and bounded chromatic number, presenting complexity results and algorithms. For bounded degree graphs, a classic result of Lov'asz yields a (k; b\\Delta=kc) coloring for graphs with E edges of maximum degree \\Delta in O(\\DeltaE) time. For graphs of bounded genus, (2; d), for d ? 0 and (3,1)- coloring are proved NP-Complete, even for planar graphs. Results of [11] easily can be transformed to (3; 2) color a...