More Web Proxy on the site http://driver.im/

article

Free access

The Complexity of Near-Optimal Graph Coloring

Authors:

D. S. JohnsonAuthors Info & Claims

Journal of the ACM (JACM), Volume 23, Issue 1

Pages 43 - 49

https://doi.org/10.1145/321921.321926

Published: 01 January 1976 Publication History

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).

References

[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

Digital Library

[2]

GAREY, M R, JOHNSON, D. S, AND STOCKMEYER, L. Some slmphfied NP-complete graph problems Theor Comput Sei (to appear).

[3]

GaA~AM, R. L Bounds on multlprocessing timing anomahes SIAM J on Appl. Math. 17 (1969), 416-429.

[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.

[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.

[6]

JOHNSON, D.S. Approximation algomthms for combmatomal problems J. Comput. and Syst. Sc~s 9 (1974), 256-278

Digital 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.

[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-326

[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.

[10]

Lov~-sz, L. (Personal commumcation.)

[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.

[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-42

[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-32

Digital Library

[14]

STOCKMEYER, L. Planar 3-colorabfllty Is polynomial complete. ACM SIGACT News 5, 3 (1973), 19-25

Digital 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.

[16]

WOOD, D. C. A techmque for coloring a graph apphcable to large scale tlme-tabhng problems. Comput. J 12 (1969), 317-319

Cited By

Larrauri AŽivný S(2024)Solving Promise Equations over Monoids and GroupsACM Transactions on Computational Logic10.1145/369810626:1(1-24)Online publication date: 27-Sep-2024
https://dl.acm.org/doi/10.1145/3698106
Nakajima TŽivný S(2024)On the Complexity of Symmetric vs. Functional PCSPsACM Transactions on Algorithms10.1145/367365520:4(1-29)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3673655
Ciardo LSobocinski PLago UEsparza J(2024)Quantum advantage and CSP complexityProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662118(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662118
Show More Cited By

Index Terms

The Complexity of Near-Optimal Graph Coloring
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Graph colouring via the discharging method
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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 23, Issue 1

Jan. 1976

220 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321921

Editor:
Edward G. Coffman

Issue’s Table of Contents

Copyright © 1976 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1976

Published in JACM Volume 23, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

243
Total Citations
View Citations
2,419
Total Downloads

Downloads (Last 12 months)337
Downloads (Last 6 weeks)33

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Larrauri AŽivný S(2024)Solving Promise Equations over Monoids and GroupsACM Transactions on Computational Logic10.1145/369810626:1(1-24)Online publication date: 27-Sep-2024
https://dl.acm.org/doi/10.1145/3698106
Nakajima TŽivný S(2024)On the Complexity of Symmetric vs. Functional PCSPsACM Transactions on Algorithms10.1145/367365520:4(1-29)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3673655
Ciardo LSobocinski PLago UEsparza J(2024)Quantum advantage and CSP complexityProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662118(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662118
Banakh DKozik MSobocinski PLago UEsparza J(2024)Injective hardness condition for PCSPsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662072(1-10)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662072
Ciardo LKozik MKrokhin ANakajima TŽivný SSobocinski PLago UEsparza J(2024)1-in-3 vs. Not-All-Equal: Dichotomy of a broken promiseProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662069(1-12)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662069
Ciardo LŽivný SMohar BShinkar IO'Donnell R(2024)Semidefinite Programming and Linear Equations vs. Homomorphism ProblemsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649635(1935-1943)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649635
Fukada KShirai TTogawa N(2024)Hybrid Iterative Annealing Method Using a Quantum Annealer and a Classical Computer2024 IEEE International Conference on Consumer Electronics (ICCE)10.1109/ICCE59016.2024.10444173(1-6)Online publication date: 6-Jan-2024
https://doi.org/10.1109/ICCE59016.2024.10444173
Pouzet M(2024)Well-quasi-ordering and Embeddability of Relational StructuresOrder10.1007/s11083-024-09664-yOnline publication date: 3-Apr-2024
https://doi.org/10.1007/s11083-024-09664-y
Dupin N(2024)Matheuristic Variants of DSATUR for the Vertex Coloring ProblemMetaheuristics10.1007/978-3-031-62922-8_7(96-111)Online publication date: 4-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-62922-8_7
Srivastava SBansal RThapar A(2023)Heuristic approach for bandwidth consecutive multi-coloring problemJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-22424245:6(9991-10002)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.3233/JIFS-224242
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents