Premium
Integer programming formulations for minimum deficiency interval coloring
Author(s) -
Bodur Merve,
Luedtke James R.
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21826
Subject(s) - mathematics , combinatorics , graph coloring , discrete mathematics , edge coloring , interval graph , fractional coloring , integer programming , greedy coloring , vertex (graph theory) , graph , line graph , pathwidth , graph power , algorithm
A proper edge‐coloring of a given undirected graph with natural numbers identified with colors is an interval (or consecutive) coloring if the colors of edges incident to each vertex form an interval of consecutive integers. Not all graphs admit such an edge‐coloring and the problem of deciding whether a graph is interval colorable is NP‐complete. For a graph that is not interval colorable, determining a graph invariant called the (minimum) deficiency is a widely used approach. Deficiency is a measure of how close the graph is to have an interval coloring. The majority of the studies in the literature either derive bounds on the deficiency of general graphs or calculate the deficiency of graphs belonging to some special graph classes. In this work, we derive integer programming formulations of the Minimum Deficiency Problem which seeks to find the exact deficiency value of a graph, given a bound on the number of colors that can be used. We further enhance the formulation by introducing a family of valid inequalities. Then, we solve our model via a branch‐and‐cut algorithm . Our computational study on a large set of random graphs illustrates the strength of our formulation and the efficiency of the proposed approach.