On Approximation Algorithms for Coloring k-Colorable Graphs

概要

論文の詳細を見る
Karger, Motwani and Sudan presented a graph coloring algorithm based on semidefinite programming, which colors any κ-colorable graph with maximum degree Δ using O^^〜(Δ^<1-2/κ>) colors. This algorithm leads to an algorithm for κ-colorable graph using O^^〜(Δ^<1-3/(κ+1)) colors. This improved Wigderson's algorithm, which uses O(n^(1-1/(κ-1)) colors, con-taining as a subroutine an algorithm using (Δ + 1) colors for graphs with maximum degree Δ. It is easy to imagine that an algorithm which uses less colors in terms of Δ leads to an al-gorithm which uses less colors in terms of n. In this paper, we consider this influence assuming that we have an algorithm which uses O^^〜(Δ^<1-χ/κ>) colors for 2 < χ < 3. Specifically, we will show that the algorithms of Karger et al., of Blum and Karger and of Halperin et al. can be improved under this assumption.
社団法人電子情報通信学会の論文
2003-05-01