Cliques, holes and the vertex coloring polytope
DOI10.1016/J.IPL.2003.11.005zbMATH Open1176.90598OpenAlexW2048483530MaRDI QIDQ1029072FDOQ1029072
Authors: Y. Frota, Manoel 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
Recommendations
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Integer programming (90C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)
Cites Work
Cited In (35)
- A one-to-one correspondence between colorings and stable sets
- Fractional programming formulation for the vertex coloring problem
- A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem
- Chromatic Gallai identities operating on Lovász number
- Crossings, colorings, and cliques
- On the recursive largest first algorithm for graph colouring
- An integer programming approach to b-coloring
- A matheuristic approach for the \(b\)-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic
- Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope
- Polyhedral studies of vertex coloring problems: the standard formulation
- Clique-connecting forest and stable set polytopes
- Packing and partitioning orbitopes
- The minimum chromatic violation problem: a polyhedral study
- MIP formulations for induced graph optimization problems: a tutorial
- Complexity of clique-coloring odd-hole-free graphs
- Facet-inducing web and antiweb inequalities for the graph coloring polytope
- Cycle-based facets of chromatic scheduling polytopes
- A branch-and-cut algorithm for the connected max-\(k\)-cut problem
- An exact algorithm for the partition coloring problem
- Revisiting the Hamiltonian \(p\)-median problem: a new formulation on directed graphs and a branch-and-cut algorithm
- A branch-and-price approach for the partition coloring problem
- A supernodal formulation of vertex colouring with applications in course timetabling
- A branch-and-cut procedure for the Udine course timetabling problem
- The maximum-impact coloring polytope
- A combined parallel Lagrangian decomposition and cutting-plane generation for maximum stable set problems
- A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
- Integer programming formulations and efficient local search for relaxed correlation clustering
- A branch-and-cut algorithm for partition coloring
- Integer linear programming formulations of the filter partitioning minimization problem
- The minimum chromatic violation problem: a polyhedral approach
- A survey on vertex coloring problems
- A branch-and-cut algorithm for equitable coloring based on a formulation by representatives
- On the asymmetric representatives formulation for the vertex coloring problem
- A column generation based algorithm for the robust graph coloring problem
- The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study
This page was built for publication: Cliques, holes and the vertex coloring polytope
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1029072)
