Cliques, holes and the vertex coloring polytope
From MaRDI portal
Publication:1029072
DOI10.1016/j.ipl.2003.11.005zbMath1176.90598OpenAlexW2048483530MaRDI QIDQ1029072
Yuri Frota, Manoel B. Campêlo, Ricardo C. Corrêa
Publication date: 9 July 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2003.11.005
Programming involving graphs or networks (90C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (32)
A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems ⋮ An exact algorithm for the partition coloring problem ⋮ A supernodal formulation of vertex colouring with applications in course timetabling ⋮ The minimum chromatic violation problem: a polyhedral study ⋮ The minimum chromatic violation problem: a polyhedral approach ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ An integer programming approach to b-coloring ⋮ Fractional programming formulation for the vertex coloring problem ⋮ A branch-and-cut algorithm for the connected max-\(k\)-cut problem ⋮ A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem ⋮ The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study ⋮ The maximum-impact coloring polytope ⋮ Packing and partitioning orbitopes ⋮ Chromatic Gallai identities operating on Lovász number ⋮ Revisiting the Hamiltonian \(p\)-median problem: a new formulation on directed graphs and a branch-and-cut algorithm ⋮ A survey on vertex coloring problems ⋮ A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives ⋮ A matheuristic approach for the \(b\)-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic ⋮ A column generation based algorithm for the robust graph coloring problem ⋮ Polyhedral studies of vertex coloring problems: the standard formulation ⋮ Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope ⋮ On the asymmetric representatives formulation for the vertex coloring problem ⋮ A branch-and-cut procedure for the Udine course timetabling problem ⋮ Clique-connecting forest and stable set polytopes ⋮ A branch-and-price approach for the partition coloring problem ⋮ A branch-and-cut algorithm for partition coloring ⋮ On the recursive largest first algorithm for graph colouring ⋮ A one-to-one correspondence between colorings and stable sets ⋮ Cycle-based facets of chromatic scheduling polytopes ⋮ Integer programming formulations and efficient local search for relaxed correlation clustering ⋮ A Branch-and-Cut Algorithm for Equitable Coloring based on a Formulation by Representatives ⋮ Integer linear programming formulations of the filter partitioning minimization problem
Cites Work
This page was built for publication: Cliques, holes and the vertex coloring polytope
