Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope

DOI10.1016/j.disopt.2016.06.003zbMath1387.05082OpenAlexW2476637836MaRDI QIDQ1751169

Phablo F. S. Moura, Marcio C. Santos, Manoel B. Campêlo

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2016.06.003

zbMATH Keywords

stable set polytopefacetlexicographic productweb graph\(k\)-fold graph coloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)

Related Items (1)

On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs

Cites Work

• Unnamed Item
• Efficient symmetry breaking formulations for the job grouping problem
• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
• Facet-inducing web and antiweb inequalities for the graph coloring polytope
• Clique-circulants and the stable set polytope of fuzzy circular interval graphs
• The stable set polytope of quasi-line graphs
• Cliques, holes and the vertex coloring polytope
• On stable set polyhedra for K//(1,3)free graphs
• n-tuple colorings and associated graphs
• A class of facet producing graphs for vertex packing polyhedra
• \(n\)-tuple coloring of planar graphs with large odd girth
• The rank facets of the stable set polytope for claw-free graphs
• The multichromatic numbers of some Kneser graphs
• Antiweb-wheel inequalities and their separation problems over the stable set polytopes
• On optimal \(k\)-fold colorings of webs and antiwebs
• Antiwebs are rank-perfect
• On the asymmetric representatives formulation for the vertex coloring problem
• A one-to-one correspondence between colorings and stable sets
• Almost all webs are not rank-perfect
• A New Facet Generating Procedure for the Stable Set Polytope
• A Class Representative Model for Pure Parsimony Haplotyping
• A Branch-And-Price Approach for Graph Multi-Coloring
• Two Results Concerning Multicoloring
• On the Facet-Inducing Antiweb-Wheel Inequalities for Stable Set Polytopes

This page was built for publication: Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope