Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope

DOI10.1051/ro/2015053zbMath1378.90058OpenAlexW2498887162MaRDI QIDQ2826670

Mónica Braga, Javier Marenco

Publication date: 18 October 2016

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ro/2015053

zbMATH Keywords

disjunctive rankacyclic coloring problemdisjunctive anti-rank

Mathematics Subject Classification ID

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

Uses Software

• ColPack

Cites Work

• On the polyhedral lift-and-project methods and the fractional stable set polytope
• On acyclic colorings of planar graphs
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Acyclic coloring of graphs of maximum degree five: nine colors are enough
• Disjunctive ranks and anti-ranks of some facet-inducing inequalities of the acyclic coloring polytope
• Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation
• Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• New Acyclic and Star Coloring Algorithms with Application to Computing Hessians
• Acyclic Colourings of Planar Graphs with Large Girth
• Acyclic coloring of graphs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
• Sherali-adams relaxations of the matching polytope
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
• A polyhedral study of the acyclic coloring problem
• Acyclic colorings of planar graphs
• Acyclic colouring of 1-planar graphs
• Unnamed Item
• Unnamed Item