A polyhedral investigation of star colorings

DOI10.1016/j.dam.2016.03.003zbMath1336.05042OpenAlexW2335094801MaRDI QIDQ284838

Marc E. Pfetsch, Christopher Hojny

Publication date: 18 May 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.03.003

zbMATH Keywords

branch-and-cutcomplete linear descriptionsparse Hessianstar coloringtotal dual integrality

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Related Items

Packing, partitioning, and covering symresacks

Uses Software

• polymake
• SCIP
• PLCP
• SQPlab
• ColPack

Cites Work

• Unnamed Item
• Unnamed Item
• Acyclic and star colorings of cographs
• The maximum \(k\)-colorable subgraph problem and orbitopes
• SCIP: solving constraint integer programs
• Packing and partitioning orbitopes
• Distance-hereditary graphs
• A generalization of antiwebs to independence systems and their canonical facets
• On certain polytopes associated with graphs
• Facets of the graph coloring polytope
• Coloring with no 2-colored \(P_4\)'s
• A branch-and-cut algorithm for graph coloring
• Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation
• Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry
• Star coloring of graphs
• New Acyclic and Star Coloring Algorithms with Application to Computing Hessians
• Estimation of sparse hessian matrices and graph coloring problems
• A Characterization of Block-Graphs
• Facet of regular 0–1 polytopes
• On the facial structure of set packing polyhedra
• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
• Numerical optimization. Theoretical and practical aspects. Transl. from the French
• Acyclic colorings of planar graphs