A polyhedral approach for the equitable coloring problem

DOI10.1016/J.DAM.2012.11.018zbMATH Open1288.05098OpenAlexW2125283791MaRDI QIDQ2448876FDOQ2448876

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

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

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)

Cites Work

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

Cited In (14)

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

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)