Graph products and chromatic numbers
- 1 January 1989
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 124-128
- https://doi.org/10.1109/sfcs.1989.63466
Abstract
The problem of computing the chromatic number of a graph is considered. No known approximation algorithm can guarantee a better than O(n/sup 0.4/) coloring on a three-chromatic graph with n vertices. Evidence is provided that it is inherently impossible to achieve a better than n/sup epsilon / ratio in polynomial time by showing that 'breaking the n/sup epsilon / barrier' will automatically lead to vastly better polynomial-time approximation algorithms that achieve ratios closer to log n.Keywords
This publication has 6 references indexed in Scilit:
- A better performance guarantee for approximate graph coloringAlgorithmica, 1990
- Distributive graph algorithms Global solutions from local dataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Improving the performance guarantee for approximate graph coloringJournal of the ACM, 1983
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972