1998/03/01 by David R. Karger, Rajeev Motwani, Madhu Sudan · 430 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Combinatorics #Semidefinite programming #Mathematics #Maximum cut #Vertex (graph theory) #Degree (music) #Binary logarithm #Graph #Duality (order theory) #Graph coloring #Linear programming #Function (biology) #Approximation algorithm #Discrete mathematics #Algorithm #Mathematical optimization
paper · doi:10.1145/274787.274791
published in Journal of the ACM 45(2), 246-265 (Association for Computing Machinery)
openalex publication_date 1998/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15
We consider the problem of coloring k -colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on n vertices with min O (Δ 1/3 log 1/2 Δ log n ), O ( n 1/4 log 1/2 n ) colors where Δ is the maximum degree of any vertex. Besides giving the best known approximation ratio in terms of n , this marks the first nontrivial approximation result as a function of the maximum degree Δ. This result can be generalized to k -colorable graphs to obtain a coloring using min O (Δ 1-2/ k log 1/2 Δ log n ), O ( n 1−3/( k +1) log 1/2 n ) colors. Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems , which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lovász θ-function. We show lower bounds on the gap between the optimum solution of our semidefinite program and the actual chromatic number; by duality this also demonstrates interesting new facts about the θ-function.