Facet-inducing web and antiweb inequalities for the graph coloring polytope
From MaRDI portal
Publication:608302
DOI10.1016/j.dam.2010.08.016zbMath1215.05073OpenAlexW2102269138MaRDI QIDQ608302
Publication date: 25 November 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2010.08.016
Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Coloring of graphs and hypergraphs (05C15)
Related Items (4)
Generating irreducible copositive matrices using the stable set problem ⋮ Chromatic Gallai identities operating on Lovász number ⋮ Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope ⋮ A note on selective line-graphs and partition colorings
Cites Work
- Pseudo-Boolean optimization
- A construction for non-rank facets of stable set polytopes of webs
- Clique-circulants and the stable set polytope of fuzzy circular interval graphs
- The stable set polytope of quasi-line graphs
- On packing and covering polyhedra of consecutive ones circulant clutters
- Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
- A class of facet producing graphs for vertex packing polyhedra
- Clique family inequalities for the stable set polytope of quasi-line graphs.
- A class of web-based facets for the generalized vertex packing problem
- Facets of the graph coloring polytope
- On the asymmetric representatives formulation for the vertex coloring problem
- Exploring the relationship between max-cut and stable set relaxations
- A one-to-one correspondence between colorings and stable sets
- Almost all webs are not rank-perfect
- On the Facet-Inducing Antiweb-Wheel Inequalities for Stable Set Polytopes
- Clique-connecting forest and stable set polytopes
- On the recursive largest first algorithm for graph colouring
This page was built for publication: Facet-inducing web and antiweb inequalities for the graph coloring polytope
