A polyhedral study of the acyclic coloring problem

DOI10.1016/J.ENDM.2009.11.007zbMATH Open1268.05064OpenAlexW2173396908MaRDI QIDQ5891089FDOQ5891089

Javier Marenco, Mónica Braga

Publication date: 19 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.11.007

Recommendations

• A polyhedral study of the acyclic coloring problem
• Acyclic coloring with few division vertices
• Facets based on cycles and cliques for the acyclic coloring polytope
• Disjunctive ranks and anti-ranks of some facet-inducing inequalities of the acyclic coloring polytope
• Improved bounds for acyclic chromatic index of planar graphs

zbMATH Keywords

polyhedral combinatoricsacyclic coloringacyclic chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Acyclic colorings of planar graphs
• Acyclic coloring of graphs
• Coloring with no 2-colored \(P_4\)'s
• A cutting plane algorithm for graph coloring
• A branch-and-cut algorithm for graph coloring
• Estimation of sparse hessian matrices and graph coloring problems
• Minimum feedback vertex set and acyclic coloring.
• The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
• Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
• Title not available (Why is that?)
• Acyclic list 7‐coloring of planar graphs

Cited In (3)

• Polychromatic Acyclic Tours in Colored Multigraphs
• 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

This page was built for publication: A polyhedral study of the acyclic coloring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5891089)