Thumbnail

Polynomial approximation and graph-coloring

Paschos, Vangelis (2003), Polynomial approximation and graph-coloring, Computing, 70, 1, p. 41-86. http://dx.doi.org/10.1007/s00607-002-1468-7

View/Open
Type
Article accepté pour publication ou publié
Date
2003
Journal name
Computing
Volume
70
Number
1
Publisher
Springer Wien
Pages
41-86
Publication identifier
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Abstract (EN)
Consider a graph G=(V,E) of order n. In the minimum graph-coloring problem we try to color V with as few colors as possible so that no two adjacent vertices receive the same color. This problem is among the first ones proved to be intractable, and hence, it is very unlikely that an optimal polynomial-time algorithm could ever be devised for it. In this paper, we survey the main polynomial time approximation algorithms (the ones for which theoretical approximability bounds have been studied) for the minimum graph-coloring and we discuss their approximation performance and their complexity. Finally, we further improve the approximation ratio for graph-coloring.
Subjects / Keywords
Graph; Coloring; Complexity; NP-complete; Approximation algorithm