Journal of Graph Theory · 1997 · 131 citations · 23 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationComputational ComplexityGraph AlgorithmsGraph ColoringGraph TheoryApproximation Algorithms For ColoringColoring Planar GraphsGraph Coloring ApproximationGraph Coloring ComplexityPlanar GraphsVertex Coloring
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. © 1997 John Wiley & Sons, Inc.
23
Choice Reviews Online · 1995 · 1.3K citations
Proof verification and hardness of approximation problems
Sanjeev Arora, Carsten Lund, R. Motwani et al. · 1992 · 744 citations
.879-approximation algorithms for MAX CUT and MAX 2SAT
Michel X. Goemans, David P. Williamson · 1994 · 239 citations · Full text