The maximum \(k\)-colorable subgraph problem and orbitopes

DOI10.1016/j.disopt.2011.04.002zbMath1233.90240OpenAlexW2086628398MaRDI QIDQ666000

Marc E. Pfetsch, Tim Januschowski

Publication date: 7 March 2012

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

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

zbMATH Keywords

integer programmingcombinatorial optimizationgraph coloringsymmetry breaking

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)

Related Items

A polyhedral investigation of star colorings, Mathematical Programming Models and Exact Algorithms, Online algorithms for the maximum \(k\)-colorable subgraph problem, The Maximum k-Colorable Subgraph Problem and Related Problems, Lexicographical order in integer programming, Polytopes associated with symmetry handling, Packing, partitioning, and covering symresacks, A polyhedral approach for the equitable coloring problem, The maximum \(k\)-colorable subgraph problem and orbitopes, Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem

Cites Work

• Unnamed Item
• Unnamed Item
• The maximum \(k\)-colorable subgraph problem and orbitopes
• Packing and partitioning orbitopes
• The node-deletion problem for hereditary properties is NP-complete
• Exact solution of bin-packing problems using column generation and branch-and-bound
• On perfectness of sums of graphs
• Geometric algorithms and combinatorial optimization.
• On certain polytopes associated with graphs
• Pruning by isomorphism in branch-and-cut
• Exploiting orbits in symmetric ILP
• On the \(k\)-coloring of intervals
• Polyhedral results for the bipartite induced subgraph problem
• Symmetric ILP: Coloring and small integers
• Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry
• Extended Formulations for Packing and Partitioning Orbitopes
• Constraint Orbital Branching
• Symmetry in Integer Linear Programming
• Fundamental Domains for Integer Programs with Symmetries
• Graph Bipartization and via minimization
• Facet of regular 0–1 polytopes
• A Column Generation Approach for Graph Coloring
• The approximation of maximum subgraph problems
• Orbitopal Fixing