Facet-inducing web and antiweb inequalities for the graph coloring polytope
From MaRDI portal
Publication:608302
DOI10.1016/J.DAM.2010.08.016zbMATH Open1215.05073OpenAlexW2102269138MaRDI QIDQ608302FDOQ608302
Authors: Gintaras Palubeckis 
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
Recommendations
- Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope
- On the Facet-Inducing Antiweb-Wheel Inequalities for Stable Set Polytopes
- Cliques, holes and the vertex coloring polytope
- Facets of the graph coloring polytope
- Almost all webs are not rank-perfect
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- A class of facet producing graphs for vertex packing polyhedra
- Pseudo-Boolean optimization
- Facets of the graph coloring polytope
- On the recursive largest first algorithm for graph colouring
- Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
- Clique family inequalities for the stable set polytope of quasi-line graphs.
- On the asymmetric representatives formulation for the vertex coloring problem
- The stable set polytope of quasi-line graphs
- On packing and covering polyhedra of consecutive ones circulant clutters
- A one-to-one correspondence between colorings and stable sets
- Almost all webs are not rank-perfect
- Exploring the relationship between max-cut and stable set relaxations
- A class of web-based facets for the generalized vertex packing problem
- On the Facet-Inducing Antiweb-Wheel Inequalities for Stable Set Polytopes
- Clique-connecting forest and stable set polytopes
- A construction for non-rank facets of stable set polytopes of webs
- Clique-circulants and the stable set polytope of fuzzy circular interval graphs
Cited In (8)
- Chromatic Gallai identities operating on Lovász number
- Cliques, holes and the vertex coloring polytope
- On the Facet-Inducing Antiweb-Wheel Inequalities for Stable Set Polytopes
- Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope
- Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope
- Disjunctive ranks and anti-ranks of some facet-inducing inequalities of the acyclic coloring polytope
- Generating irreducible copositive matrices using the stable set problem
- A note on selective line-graphs and partition colorings
This page was built for publication: Facet-inducing web and antiweb inequalities for the graph coloring polytope
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q608302)
