New integer linear programming models for the vertex coloring problem

DOI10.1007/978-3-319-77404-6_47zbMath1504.68167arXiv1706.10191OpenAlexW2964124125MaRDI QIDQ2294722

Adalat Jabrayilov, Petra Mutzel

Publication date: 12 February 2020

Full work available at URL: https://arxiv.org/abs/1706.10191

zbMATH Keywords

graph coloringinteger linear programmingvertex coloring

Mathematics Subject Classification ID

Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (11)

Graph Coloring Lower Bounds from Decision Diagrams ⋮ Improving lower bounds for equitable chromatic number ⋮ The Parallel Quantum Algorithm for the Class of Optimization ⋮ Total coloring and total matching: polyhedra and facets ⋮ Collective dynamics of phase-repulsive oscillators solves graph coloring problem ⋮ New Steiner 2-designs from old ones by paramodifications ⋮ Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments ⋮ An incremental search heuristic for coloring vertices of a graph ⋮ Integer linear programming formulations of the filter partitioning minimization problem ⋮ On recognizing staircase compatibility ⋮ Graph coloring with decision diagrams

Uses Software

• SCIP
• Gurobi

This page was built for publication: New integer linear programming models for the vertex coloring problem