A first exploration of the split-interval coloring polytope

Abstract

Given a graph G = (V,E), a set of consecutive colors, and a demand vector d ∈ ℤ+|V|, the interval coloring problem asks for an assignment of di consecutive colors to each vertex i ϵ V, in such a way that no two adjacent vertices are assigned the same color. Inspired by a situation arising in the allocation of ships to berths, in this work we propose to consider the split-interval coloring problem, which asks to assign at most two disjoint color intervals to each vertex in such a way that each vertex i ϵ V receives a total of di colors. We explore a natural integer programming formulation for this NP-hard problem and its associated polytope. We state some relations to the interval coloring polytope, including lemmas allowing to translate valid inequalities between these two polytopes. We also present several valid inequalities and study conditions ensuring that these inequalities induce facets of the associated polytope.