Efficient bounds on a branch and bound algorithm for graph colouration

DOI10.1080/0020739910220516MaRDI QIDQ4009325zbMATH OpenOpenAlexFDO

Authors Sydney C. K. Chu

Publication date 27 September 1992

Published in International Journal of Mathematical Education in Science and Technology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/0020739910220516

zbMATH Keywords

bound algorithmchromatic polynomialgraph colouration

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• scientific article; zbMATH DE number 956855
• scientific article; zbMATH DE number 956852
• Algorithmic bounds for the chromatic number†
• Bounding vertex coloring by truncatedmultistage branch and bound
• Graphs with small chromatic numbers are easy to color

Cites work

• A note on the complexity of the chromatic number problem
• A theoretical analysis of backtracking in the graph coloring problem
• Algorithm 457: finding all cliques of an undirected graph
• An Algorithm for Determining the Chromatic Number of a Graph
• An algorithm for obtaining the chromatic number and an optimal coloring of a graph
• An Algorithm for the Chromatic Number of a Graph
• An algorithm for the chromatic number of a graph
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• scientific article; zbMATH DE number 4039250 (Why is no real title available?)
• Some Examples of Combinatorial Averaging

Cited in

(10)

• Efficient algorithms for acyclic colorings of graphs
• Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
• A Wide Branching Strategy for the Graph Coloring Problem
• Improved bounds for the chromatic number of a graph
• A Game Theoretic Approach for Efficient Graph Coloring
• scientific article; zbMATH DE number 1043838 (Why is no real title available?)
• scientific article; zbMATH DE number 7566051 (Why is no real title available?)
• Bounds and fixed-parameter algorithms for weighted improper coloring
• A simple branching scheme for vertex coloring problems
• Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs

This page was built for publication: Efficient bounds on a branch and bound algorithm for graph colouration

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