Algorithmic bounds for the chromatic number†

DOI10.1080/02331930701779021MaRDI QIDQ5449019zbMATH OpenOpenAlexFDO

Authors Ingo Schiermeyer

Publication date 10 March 2008

Published in Optimization (Search for Journal in Brave)

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

zbMATH Keywords

algorithmgraph colouring

Mathematics Subject Classification ID

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

Recommendations

• An approximate algorithm for the chromatic number of graphs
• New upper bounds for the chromatic number of a graph
• scientific article; zbMATH DE number 1189240
• An upper bound for the chromatic number of line graphs
• Bounds for the chromatic number of a graph

Cites work

• scientific article; zbMATH DE number 1286500 (Why is no real title available?)
• A strengthening of Brooks' theorem
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Graph Theory and Probability
• New upper bounds for the chromatic number of a graph
• On Brooks' Theorem for Sparse Graphs
• Recognizing Berge graphs
• The smallest triangle-free 4-chromatic 4-regular graph
• The strong perfect graph theorem
• Three short proofs in graph theory
• Vertex colouring and forbidden subgraphs -- a survey

Cited in

(18)

• New upper bounds for the chromatic number of a graph
• Graph coloring approach with new upper bounds for the chromatic number: team building application
• Algorithmic discrepancy beyond partial coloring
• scientific article; zbMATH DE number 1405798 (Why is no real title available?)
• Efficient bounds on a branch and bound algorithm for graph colouration
• scientific article; zbMATH DE number 1998817 (Why is no real title available?)
• An approximate algorithm for the chromatic number of graphs
• On the hardness of approximating the chromatic number
• An algorithm to determine the chromatic number of a graph
• The chromatic discrepancy of graphs
• A bound on the total chromatic number
• Exact Algorithms for a One-defective Vertex Colouring Problem
• Three new upper bounds on the chromatic number
• scientific article; zbMATH DE number 4087683 (Why is no real title available?)
• Bounds for the chromatic number of a graph
• Improved bounds for the chromatic number of a graph
• Bounded vertex colorings of graphs
• Efficient algorithms for finding critical subgraphs

This page was built for publication: Algorithmic bounds for the chromatic number†

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