On the asymmetric representatives formulation for the vertex coloring problem

DOI10.1016/j.dam.2007.05.058zbMath1138.05020MaRDI QIDQ2482105

Victor A. Campos, Ricardo C. Corrêa, Manoel B. Campêlo

Publication date: 16 April 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.05.058

zbMATH Keywords

graph coloring; combinatorial problems; chromatic number; facets of polyhedra

Mathematics Subject Classification ID

90C10: Integer programming

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

A branch‐and‐price approach to k‐clustering minimum biclique completion problem, A branch‐and‐cut algorithm for the ring spur assignment problem, Fractional programming formulation for the vertex coloring problem, Facet-inducing web and antiweb inequalities for the graph coloring polytope, A supernodal formulation of vertex colouring with applications in course timetabling, A computational comparison of several models for the exact solution of the capacity and distance constrained plant location problem, A polyhedral approach for the equitable coloring problem, Chromatic Gallai identities operating on Lovász number, Polyhedral results for the Equitable Coloring Problem, A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems, A survey on vertex coloring problems

Cites Work

• Unnamed Item
• Unnamed Item
• An exact algorithm for the maximum clique problem
• Cliques, holes and the vertex coloring polytope
• Facets of the graph coloring polytope
• A Column Generation Approach for Graph Coloring