On approximating the b-chromatic number

We consider the problem of approximating the b-chromatic number of a graph. We show that there is no constant ɛ > 0 for which this problem can be approximated within a factor of 120 / 133 - ɛ in polynomial time, unless P = NP . This is the first hardness result for approximating the b-chromatic n...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2005-02, Vol.146 (1), p.106-110
Main Authors: Corteel, Sylvie, Valencia-Pabon, Mario, Vera, Juan-Carlos
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Approximation algorithms
Combinatorial problems
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Graph coloring
Graph theory
Mathematics
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of approximating the b-chromatic number of a graph. We show that there is no constant ɛ > 0 for which this problem can be approximated within a factor of 120 / 133 - ɛ in polynomial time, unless P = NP . This is the first hardness result for approximating the b-chromatic number.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2004.09.006