Safe Lower Bounds for Graph Coloring

DOI10.1007/978-3-642-20807-2_21zbMath1341.05074OpenAlexW1844333864MaRDI QIDQ3009768

Stephan Held, Edward 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 generationgraph coloringfractional chromatic numbermaximum-weight stable setsafe computations

Mathematics Subject Classification ID

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

Related Items

A branch and price algorithm for list coloring problem ⋮ An integer programming approach to b-coloring ⋮ The maximum-impact coloring polytope ⋮ Coordinated cutting plane generation via multi-objective separation ⋮ Exact weighted vertex coloring via branch-and-price ⋮ A new \textsf{DSATUR}-based algorithm for exact vertex coloring

Uses Software

• Cliquer

Cites Work

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

This page was built for publication: Safe Lower Bounds for Graph Coloring