On the complexity of the minimum chromatic violation problem

DOI10.1007/978-3-031-60924-4_12MaRDI QIDQ7030727zbMATH OpenFDO

Authors Diego Delle Donne, Mariana S. Escalante, María Elisa Ugarte

Publication date 7 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-60924-4_12

zbMATH Keywords

complexitygraph coloringchromatic violation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Coloring of graphs and hypergraphs (05C15)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A graph coloring algorithm for large scheduling problems
• A new approach on locally checkable problems
• A supernodal formulation of vertex colouring with applications in course timetabling
• An introduction to timetabling
• Exploring the complexity boundary between coloring and list-coloring
• Frequency assignment in cellular phone networks
• Network flows. Theory, algorithms, and applications.
• On the \(k\)-coloring of intervals
• Precoloring extension on unit interval graphs
• Precoloring extension. I: Interval graphs
• The ellipsoid method and its consequences in combinatorial optimization
• The minimum chromatic violation problem: a polyhedral approach
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

This page was built for publication: On the complexity of the minimum chromatic violation problem

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