An exact graph coloring algorithm using color exchange

MaRDI QIDQ1374088zbMATH OpenFDO

Authors J. Ning

Publication date 2 December 1997

Published in Journal of the Egyptian Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

algorithmchromatic numbercoloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (including graph drawing) in computer science (68R10)

Review text

The authors apply a method based on a theorem of Berge and give an algorithm for coloring the vertices of a graph. The original Berge algorithm, a modified version of it, and a simple branch-and-bound backtracking algorithm are executed on PC AT 486 computer to produce an exact coloring function. The authors' implementation has the merit that it does not require a large amount of memory.

Recommendations

• scientific article; zbMATH DE number 4006291
• scientific article; zbMATH DE number 956855
• A Pruning Procedure for Exact Graph Coloring
• An exact method for graph coloring

Cited in

(5)

• An exact method for graph coloring
• Exact Algorithms for Coloring Graphs While Avoiding Monochromatic Cycles
• scientific article; zbMATH DE number 4006291 (Why is no real title available?)
• On the greatest number of 2 and 3 colorings of a (v, e)-graph
• scientific article; zbMATH DE number 956855 (Why is no real title available?)

This page was built for publication: An exact graph coloring algorithm using color exchange

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