Defective coloring revisited

✍ Scribed by Cowen, Lenore; Goddard, Wayne; Jesurum, C. Esther

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 164 KB
• Volume: 24
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199703)24:3<205::aid-jgt2>3.0.co;2-t

✦ Synopsis

A graph is (k, d)-colorable if one can color the vertices with k colors such that no vertex is adjacent to more than d vertices of its same color. In this paper we investigate the existence of such colorings in surfaces and the complexity of coloring problems. It is shown that a toroidal graph is (3, 2)-and (5, 1)-colorable, and that a graph of genus γ is (χ γ /(d + 1) + 4, d)-colorable, where χ γ is the maximum chromatic number of a graph embeddable on the surface of genus γ. It is shown that the (2, k)-coloring, for k ≥ 1, and the (3, 1)-coloring problems are NP-complete even for planar graphs. In general graphs (k, d)-coloring is NP-complete for k ≥ 3, d ≥ 0. The tightness is considered. Also, generalizations to defects of several algorithms for approximate (proper) coloring are presented.