A polyhedral approach to the adjacent vertex distinguishable proper edge coloring problem

BRIAN CURCIO; ISABEL MÉNDEZ-DÍAZ; PAULA ZABALA

Santiago

Conferencia; XVIII Latin-Iberoamerican Conference on Operations Research, CLAIO 2016; 2016

Industrial and Systems Engineering Department of the Pontificia Universidad Católica de Chile, Latin-Ibero-American Operations Research Society (ALIO), Instituto Chileno de Investigación Operativa (ICHIO)

The adjacent vertex distinguishable proper edge coloring problem is the problem of findingthe minimum number of colors required for a proper edge coloring such that every pair ofadjacent vertices is distinguishable.In this paper we propose an integer linear programming approach to solve the problem. Westudy the underlying polyhedron, develop a Branch and Cut algorithm and present computational results that show a very good performance of the algorithm on random graphs.