2023-03-21T01:48:34Z
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
ONO, Takao
HIRATA, Tomio
open access
Copyright (C) 2003 IEICE
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.
Institute of Electronics, Information and Communication Engineers
2003-05-01
eng
journal article
VoR
http://hdl.handle.net/2237/15063
https://nagoya.repo.nii.ac.jp/records/13168
http://www.ieice.org/jpn/trans_online/index.html
0916-8508
IEICE transactions on fundamentals of electronics, communications and computer sciences
E86-A
5
1046
1051
https://nagoya.repo.nii.ac.jp/record/13168/files/462.pdf
application/pdf
236.1 kB
2018-02-20