| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10328517 | Discrete Applied Mathematics | 2005 | 5 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sylvie Corteel, Mario Valencia-Pabon, Juan-Carlos Vera,