Safe lower bounds for graph coloring

DOI10.1007/978-3-642-20807-2_21MaRDI QIDQ3009768zbMATH OpenOpenAlexFDO

Authors Stephan Held, E. C. Sewell, William Cook

Publication date 24 June 2011

Published in Integer Programming and Combinatoral Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-20807-2_21

zbMATH Keywords

column generationfractional chromatic numbergraph coloringmaximum-weight stable setsafe computations

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Maximum-weight stable sets and safe lower bounds for graph coloring
• A Column Generation Approach for Graph Coloring
• Exact solution of graph coloring problems via constraint programming and column generation
• Bounding vertex coloring by truncatedmultistage branch and bound
• Lower bounding techniques for DSATUR-based branch and bound

Cites work

• A branch-and-cut algorithm for graph coloring
• A Column Generation Approach for Graph Coloring
• A cutting plane algorithm for graph coloring
• A fast algorithm for the maximum weight clique problem
• A new algorithm for the maximum-weight clique problem
• A survey on vertex coloring problems
• An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring
• An exact approach for the vertex coloring problem
• Bounding vertex coloring by truncatedmultistage branch and bound
• Exact solution of graph coloring problems via constraint programming and column generation
• Exact solutions to linear programming problems
• Finding a Maximum Clique in an Arbitrary Graph
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• New methods to color the vertices of a graph
• On the hardness of approximating minimization problems
• Quantum annealing of the graph coloring problem
• Sur le coloriage des graphs

Cited in

(13)

• On lower bounds for numbered complete graphs
• A new \textsf{DSATUR}-based algorithm for exact vertex coloring
• Maximum-weight stable sets and safe lower bounds for graph coloring
• A branch and price algorithm for list coloring problem
• An integer programming approach to b-coloring
• Coordinated cutting plane generation via multi-objective separation
• The maximum-impact coloring polytope
• Lower bounding techniques for DSATUR-based branch and bound
• Exact weighted vertex coloring via branch-and-price
• Graph coloring lower bounds from decision diagrams
• A parallel lagrangian heuristic for the fractional chromatic number of a graph
• scientific article; zbMATH DE number 7746012 (Why is no real title available?)
• Solving the list coloring problem through a branch-and-price algorithm

Describes a project that uses

Uses Software

• Cliquer

This page was built for publication: Safe lower bounds for graph coloring

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