A comparison of integer and constraint programming models for the deficiency problem

•We describe integer and constraint programming models for the deficiency problem.•We obtain bounds on the number of colors in an edge-coloring with minimum deficiency.•We clearly show that symmetry breaking constraints decrease the computing time.

An edge-coloring of a graph G=(V,E)G=(V,E) is a function c that assigns an integer c(e  ) (called color) in {0,1,2,…}{0,1,2,…} to every edge e∈Ee∈E so that adjacent edges are assigned different colors. An edge-coloring is compact if the colors of the edges incident to every vertex form a set of consecutive integers. The deficiency problem is to determine the minimum number of pendant edges that must be added to a graph such that the resulting graph admits a compact edge-coloring. We propose and analyze three integer programming models and one constraint programming model for the deficiency problem.