M. R. Garey
D. S. Johnson
Abstract
Graph coloring problems, in which one would like to color the vertices of a given graph with a small number of colors so that no two adjacent vertices receive the same color, arise in many applications, including various scheduling and partitioning problems. In this paper the complexity and performance of algorithms which construct such colorings are investigated. For a graph G, let χ(G) denote the minimum possible number of colors required to color G and, for any graph coloring algorithm A, let A(G) denote the number of colors used by A when applied to G. Since the graph coloring problem is known to be “NP-complete,” it is considered unlikely that any efficient algorithm can guarantee A(G) = χ(G) for all input graphs. In this paper it is proved that even coming close to khgr;(G) with a fast algorithm is hard. Specifically, it is shown that if for some constant r < 2 and constant d there exists a polynomial-time algorithm A which guarantees A(G) ≤ r·χ(G) + d, then there also exists a polynomial-time algorithm A which guarantees A(G) = χ(G).
- 1 AHo, A. V, HOPCROFT, J. E, AND ULLMAN, J. D The Design and Analysis of Computer Algomthms. Addison-Wesley, Reading, Mass , 1974, Chap 10 Google Scholar
Digital Library
- 2 GAREY, M R, JOHNSON, D. S, AND STOCKMEYER, L. Some slmphfied NP-complete graph problems Theor Comput Sei (to appear).Google Scholar
- 3 GaA~AM, R. L Bounds on multlprocessing timing anomahes SIAM J on Appl. Math. 17 (1969), 416-429.Google Scholar
- 4 HILTON, A J. W., RADO, R., AND SCOTT, S. H. A (<5)-colour theorem for planar graphs. Bull. London Math. Soc. 5 (1973), 302-306.Google ScholarCross Ref
- 5 BARRA, O I-I , AND KIM, C.E. Fast approximation algorithms for the knapsack and sum of ubset problems Tech. Rep 74-13, Dep of Computer, Informatmn, and Control Sciences, U. of Minnesota, Mmneapohs, Minn., 1974.Google Scholar
- 6 JOHNSON, D.S. Approximation algomthms for combmatomal problems J. Comput. and Syst. Sc~s 9 (1974), 256-278Google ScholarDigital Library
- 7 JOHNSON, D. S Worst case behavior of graph coloring algorithms Proc of the Fifth Southeastern Conf on Combmatorlcs, Graph Theory, and Computing, Utflltas Mathemat~ca Pubfishing, Winmpeg, Canada, 1974, pp 513-528.Google Scholar
- 8 JOHNSON, D S , DEMERS, A, ULLMAN, J D , GAREY, M. R , AND GRAHAM, R. L Worst-case performance bounds for simple one-dimensional packing algomthms SIAM J Comput. 8 (1974), 299-326Google Scholar
- 9 KARP, R M Reduclblhty among combmatomal problems. In Complexzty of Computer Computations, R E. Miller and J W. Thatcher, Eds, Plenum Press, New York, 1972, pp 85-104.Google Scholar
- 10 Lov~-sz, L. (Personal commumcation.)Google Scholar
- 11 MATULA, D. M, MARBLE, G, AND ISAACSON, J D Graph coloring algorithms In Graph Theory and Computing, R. C Read, Ed., Academic Press, New York, 1972, pp 109-122.Google Scholar
- 12 ROSI!INKRANTZ, D J., STEARNS, R. E, AND LEWIS, P M Approximate algorithms for the traveling salesperson problem Proc 15th Annual Symp. on Switching and Automata Theory, IEEE, 1974, pp 33-42Google Scholar
- 13 SAHNI, S, AND GONZALES, T. P-Complete problems and approximate solutions Proc. 15th Annual Symp on Switching and Automata Theory, IEEE, 1974, pp. 28-32Google ScholarDigital Library
- 14 STOCKMEYER, L. Planar 3-colorabfllty Is polynomial complete. ACM SIGACT News 5, 3 (1973), 19-25 Google ScholarDigital Library
- 15 WELSH, D J A., AND POWELL, M. B An upper bound to the chromatic number of a graph and its apphcatlon to time tabhng problems Comput J 10 (1967), 85-86.Google Scholar
- 16 WOOD, D. C. A techmque for coloring a graph apphcable to large scale tlme-tabhng problems. Comput. J 12 (1969), 317-319Google ScholarCross Ref
Index Terms
- The Complexity of Near-Optimal Graph Coloring
Recommendations
Graph edge colouring: Tashkinov trees and Goldberg's conjecture
For the chromatic index @g^'(G) of a (multi)graph G, there are two trivial lower bounds, namely the maximum degree @D(G) and the density W(G)=max"H"@__ __"G","|"V"("H")"|">="2@__ __|E(H)|/@__ __|V(H)|/2@__ __@__ __. A famous conjecture due to Goldberg [...
Parameterized complexity of vertex colouring
For a family F of graphs and a nonnegative integer k, F + ke and F - ke, respectively, denote the families of graphs that can be obtained from F graphs by adding and deleting at most k edges, and F + kv denotes the family of graphs that can be made into ...
Comments