article

Free access

New methods to color the vertices of a graph

Author:

Daniel BrélazAuthors Info & Claims

Communications of the ACM, Volume 22, Issue 4

Pages 251 - 256

https://doi.org/10.1145/359094.359101

Published: 01 April 1979 Publication History

PDF eReader

Abstract

This paper describes efficient new heuristic methods to color the vertices of a graph which rely upon the comparison of the degrees and structure of a graph. A method is developed which is exact for bipartite graphs and is an important part of heuristic procedures to find maximal cliques in general graphs. Finally an exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs, and the new heuristic methods, the classical methods, and the exact method are compared.

References

[1]

Berge, C. Graphs and Hypergraphs. North-Holland Pub. Co., Amsterdam, 1973.

Digital Library

Google Scholar

[2]

Brelaz, D., de Werra, D., and Nicolier, Y. Compactness and balancing in scheduling. Zeitschrifi fdr Operations Research, Band 21, Heft l, Serie A, 1977, pp. 65-73.

Google Scholar

[3]

Dunstan, F. Greedy algorithms for optimization problems. Presented at Euro I meeting, Brussels, Jan. 1975.

Google Scholar

[4]

Karp, R.M. Reducibility among combinatorial problems. In Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, Eds., Plenum Press, New York and London, 1972, pp. 85- 103.

Crossref

Google Scholar

[5]

Matula, D., Marble, G., and Isaacson, J. Graph coloring algorithms. In Graph Theory and Computing, Academic Press, New York, 1972, pp. 109-122.

Crossref

Google Scholar

[6]

Randall-Brown, J. Chromatic scheduling and the chromatic number problems. Management Science 19, 4 (Dec. 1972), Part l, 456-463.

Google Scholar

[7]

Tehrani, A. Un algorithme de coloration. Cabiers du centre d'etudes de Recherche Operationnelle, Vol. 17, 2-3-4, 1975, pp. 395- 398.

Google Scholar

[8]

Welsh, D.J.A., and Powell, M.B. An upper bound for the chromatic number of a graph and its applications to timetabling problems. The Comptr. J. 10 (1967), 85-86.

Crossref

Google Scholar

Cited By

View all

Chemaa SKout ADjelloul HHarrag N(2024)Parallel Discrete Harmony Search Algorithm for the Graph Coloring ProblemEngineering, Technology & Applied Science Research10.48084/etasr.856514:5(17317-17323)Online publication date: 9-Oct-2024
https://doi.org/10.48084/etasr.8565
KAWAKAMI SMUKASA YBAO SBA DARAI JYAGI STERAMOTO JTOGAWA N(2024)Ising-Machine-Based Solver for Constrained Graph Coloring ProblemsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2023KEP0003E107.A:1(38-51)Online publication date: 1-Jan-2024
https://doi.org/10.1587/transfun.2023KEP0003
Wu ZYuan Dai LWang YWang SBergman K(2024)Flexible silicon photonic architecture for accelerating distributed deep learningJournal of Optical Communications and Networking10.1364/JOCN.49737216:2(A157)Online publication date: 9-Jan-2024
https://doi.org/10.1364/JOCN.497372
Show More Cited By

New methods to color the vertices of a graph
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

Acyclic coloring with few division vertices

An acyclic k-coloring of a graph G is a mapping @f from the set of vertices of G to a set of k distinct colors such that no two adjacent vertices receive the same color and @f does not contain any bichromatic cycle. In this paper we prove that every ...
List-coloring the square of a subcubic graph

The square G² of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G²) ≤ 7. Kostochka and Woodall ...
Optical graph 3-colorability
OSC'10: Proceedings of the Third international conference on Optical supercomputing

The graph 3-colorability problem is a decision problem in graph theory which asks if it is possible to assign a color to each vertex of a given graph using at most three colors, satisfying the condition that every two adjacent vertices have different ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 22, Issue 4

April 1979

46 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359094

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

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 April 1979

Published in CACM Volume 22, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1,189
Total Citations
View Citations
6,696
Total Downloads

Downloads (Last 12 months)696
Downloads (Last 6 weeks)100

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chemaa SKout ADjelloul HHarrag N(2024)Parallel Discrete Harmony Search Algorithm for the Graph Coloring ProblemEngineering, Technology & Applied Science Research10.48084/etasr.856514:5(17317-17323)Online publication date: 9-Oct-2024
https://doi.org/10.48084/etasr.8565
KAWAKAMI SMUKASA YBAO SBA DARAI JYAGI STERAMOTO JTOGAWA N(2024)Ising-Machine-Based Solver for Constrained Graph Coloring ProblemsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2023KEP0003E107.A:1(38-51)Online publication date: 1-Jan-2024
https://doi.org/10.1587/transfun.2023KEP0003
Wu ZYuan Dai LWang YWang SBergman K(2024)Flexible silicon photonic architecture for accelerating distributed deep learningJournal of Optical Communications and Networking10.1364/JOCN.49737216:2(A157)Online publication date: 9-Jan-2024
https://doi.org/10.1364/JOCN.497372
Marchetti KSevaljevic ADiviney AEardley CPhillips RKhadka RIgbokwe DBodily PMonga MLonati VBarendsen ESheard JPaterson J(2024)Redux: An Interactive, Dynamic Knowledge Base for Teaching NP-completenessProceedings of the 2024 on Innovation and Technology in Computer Science Education V. 110.1145/3649217.3653544(255-261)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1145/3649217.3653544
Chowdhury AMurthy C(2024)Half-Duplex APs With Dynamic TDD Versus Full-Duplex APs in Cell-Free SystemsIEEE Transactions on Communications10.1109/TCOMM.2024.336153072:7(3856-3872)Online publication date: Jul-2024
https://doi.org/10.1109/TCOMM.2024.3361530
Mussbah MSchwarz SRupp M(2024)Beam-Domain-Based Pilot Assignment for Energy Efficient Cell-Free Massive MIMOIEEE Communications Letters10.1109/LCOMM.2024.343688628:9(2176-2180)Online publication date: Sep-2024
https://doi.org/10.1109/LCOMM.2024.3436886
Chowdhury AMurthy C(2024)Pilot Length Minimization via AP-UE Clustering in Cell-Free SystemsICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP48485.2024.10447151(9216-9220)Online publication date: 14-Apr-2024
https://doi.org/10.1109/ICASSP48485.2024.10447151
Riviello DDe Filippo BAhmad BGuidotti AVanelli-Coralli A(2024)Location-based User Scheduling through Graph Coloring for Cell-Free MIMO NTN Systems2024 Joint European Conference on Networks and Communications & 6G Summit (EuCNC/6G Summit)10.1109/EuCNC/6GSummit60053.2024.10597125(652-657)Online publication date: 3-Jun-2024
https://doi.org/10.1109/EuCNC/6GSummit60053.2024.10597125
Matsuo RRaymond RYamashita SMinato SKim T(2024)Optimizing Decision Diagrams for Measurements of Quantum CircuitsProceedings of the 29th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC58780.2024.10473869(134-139)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1109/ASP-DAC58780.2024.10473869
Terci GAbdulhalik EBayrakci ABoz B(2024)BitEA: BitVertex Evolutionary Algorithm to Enhance Performance for Register AllocationIEEE Access10.1109/ACCESS.2024.344659612(115497-115514)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3446596
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Abstract

References

Cited By

Recommendations

Acyclic coloring with few division vertices

List-coloring the square of a subcubic graph

Optical graph 3-colorability

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations