New methods to color the vertices of a graph

1979/04/01 by Daniel Brélaz · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Artificial intelligence #Bipartite graph #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Graph #Graph Labeling and Dimension Problems #Heuristic #Mathematics #Theoretical computer science

paper · pdf · doi:10.1145/359094.359101

openalex publication_date 1979/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

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.

Citations

• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Reducibility among Combinatorial Problems

Cited by

• Weighted Statistical Binning: Enabling Statistically Consistent Genome-Scale Phylogenetic Analyses
• Graph Colouring: A Visual Tour
• Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
• How Much Frequency Can Be Reused in 5G Cellular Networks---A Matrix Graph Model
• Graph coloring [wikipedia]