Finding the chromatic number by means of critical graphs

DOI10.1145/944618.944628MaRDI QIDQ5463425zbMATH OpenOpenAlexFDO

Authors Francine Herrmann, Alain Hertz

Publication date 4 August 2005

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL http://www.jea.acm.org/2002/HerrmannChromatic/

zbMATH Keywords

algorithmsexperimentationperformance

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Finding the chromatic number by means of critical graphs
• Efficient algorithms for finding critical subgraphs
• New Algorithm for Chromatic Number of Graphs and their Applications
• scientific article; zbMATH DE number 4006291
• An algorithm to determine the chromatic number of a graph

Cited in

(15)

• On edge orienting methods for graph coloring
• Algorithms for a shared resource scheduling problem in which some level of conflict is tolerable
• The general \(\alpha \)-decomposition problem of fuzzy relations
• A semidefinite programming-based heuristic for graph coloring
• Coloring graphs by iterated local search traversing feasible and infeasible solutions
• Efficient algorithms for finding critical subgraphs
• Embedding a novel objective function in a two-phased local search for robust vertex coloring
• An exact method for graph coloring
• Finding the chromatic number by means of critical graphs
• An exact algorithm with learning for the graph coloring problem
• An exact approach for the vertex coloring problem
• Complexity of coloring random graphs: an experimental study of the hardest region
• On the chromatic number of graphs
• Solution techniques for the large set covering problem
• Variable space search for graph coloring

This page was built for publication: Finding the chromatic number by means of critical graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5463425)