A polyhedral approach for the equitable coloring problem

DOI10.1016/J.DAM.2012.11.018MaRDI QIDQ2448876zbMATH OpenOpenAlexFDO

Authors D. Severín, Isabel Méndez-Díaz, G. Nasini

Publication date 5 May 2014

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

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

zbMATH Keywords

integer programmingequitable graph coloringcut and branch

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Polyhedral results for the equitable coloring problem
• Equitable coloring of some convex polytope graphs
• scientific article; zbMATH DE number 1302199
• scientific article; zbMATH DE number 7058467
• Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
• Structural parameterizations for equitable coloring
• A fast algorithm for equitable coloring
• A DSATUR-based algorithm for the equitable coloring problem
• A tabu search heuristic for the equitable coloring problem
• An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem

Cites work

• scientific article; zbMATH DE number 1833421 (Why is no real title available?)
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• A branch-and-cut algorithm for equitable coloring based on a formulation by representatives
• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
• A cutting plane algorithm for graph coloring
• A polyhedral approach for the equitable coloring problem
• Conflict-free star-access in parallel memory systems
• Equitable Coloring
• Equitable coloring of trees
• Graph Colorings
• On the asymmetric representatives formulation for the vertex coloring problem
• Packing and partitioning orbitopes
• Perfect Graphs and an Application to Optimizing Municipal Services
• Testing cut generators for mixed-integer linear programming
• The equitable colorings of Kneser graphs
• The maximum \(k\)-colorable subgraph problem and orbitopes

Cited in

(14)

• Solving vertex coloring problems as maximum weight stable set problems
• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
• A flow based pruning scheme for enumerative equitable coloring algorithms
• Equitable coloring of some convex polytope graphs
• An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem
• scientific article; zbMATH DE number 7058467 (Why is no real title available?)
• Proportional choosability: a new list analogue of equitable coloring
• A fast algorithm for equitable coloring
• Polyhedral results for the equitable coloring problem
• A DSATUR-based algorithm for the equitable coloring problem
• A polyhedral approach for the equitable coloring problem
• A tabu search heuristic for the equitable coloring problem
• Improving lower bounds for equitable chromatic number
• Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings

This page was built for publication: A polyhedral approach for the equitable coloring problem

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