2023-03-25T04:22:20Z
https://nagoya.repo.nii.ac.jp/oai
oai:nagoya.repo.nii.ac.jp:00013168
2023-01-16T04:00:16Z
320:321:322
On Approximation Algorithms for Coloring k-Colorable Graphs
XIE, Xuzhen
41552
ONO, Takao
41553
HIRATA, Tomio
41554
graph coloring
approximation algorithms
NP-hard
maximum degree
Karger, Motwani and Sudan presented a graph coloring algorithm based on semidefinite programming, which colors any k-colorable graph with maximum degree Δ using Õ(Δ^1-2/k) colors. This algorithm leads to an algorithm for k-colorable graph using Õ(n ^1-3/^(k+1)) colors. This improved Wigderson's algorithm, which uses O(n^1-1/^(k-1)) colors, containing 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 algorithm which uses less colors in terms of n. In this paper, we consider this influence assuming that we have an algorithm which uses Õ(Δ^1-x/k) colors for 2<x<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.
journal article
Institute of Electronics, Information and Communication Engineers
2003-05-01
application/pdf
IEICE transactions on fundamentals of electronics, communications and computer sciences
5
E86-A
1046
1051
http://www.ieice.org/jpn/trans_online/index.html
http://hdl.handle.net/2237/15063
0916-8508
https://nagoya.repo.nii.ac.jp/record/13168/files/462.pdf
eng
http://www.ieice.org/jpn/trans_online/index.html
Copyright (C) 2003 IEICE