Distance-based polytope for the classical vertex coloring problem in graphs

• Bruno Dias UFAM
• Rosiane de Freitas UFAM
• Javier Marenco Universidad de Buenos Aires
• Nelson Maculan UFRJ

DOI: https://doi.org/10.5753/etc.2018.3157

Abstract

In this work, we present a distance-based model for the classic vertex coloring problem in graphs (VCP). The integer linear programming formulation uses decision variables representing the distance between the colors assigned to every pair of distinct vertices instead of explicitly providing the colors assigned to each vertex. We show close relations between this formulation and the socalled orientation model for VCP, also proposed by the authors of this work. In particular, we prove that we can translate many facet-inducing inequalities for the orientation model polytope into facet-inducing inequalities for the distance model polytope, and vice versa.

References

Burke, E., Mareček, J., Parkes, A., and Rudová, H. (2010). A supernodal formulation of vertex colouring with applications in course timetabling. Annals of Operat. Research, 179:105–130.

Campêlo, M., Campos, V., and Corrêa, R. (2008). On the asymmetric representatives formulation for the vertex coloring problem. Discrete Applied Mathematics, 156:1097–1111.

de Freitas, R., Dourado, M., and Szwarcfiter, J. (2010). Graph coloring and scheduling problems. 4th Latin American Workshop on Cliques in Graphs.

Dias, B. (2014). Modelos teóricos e algoritmos para a otimização da alocação de canais em redes móveis sem fio. Master’s thesis, Instituto de Computação – Universidade Federal do Amazonas, in portuguese.

Dias, B., de Freitas, R., Maculan, N., and Marenco, J. (2017). Facet-inducing inequalities and a cut-and-branch for the bandwidth coloring polytope based on the orientation model. Electronic Notes in Discrete Mathematics, 62:141 – 146. LAGOS’17 – IX Latin and American Algorithms, Graphs and Optimization.

Dias, B. R. C., Rodrigues, R. F., and Szwarcfiter, J. (2013). On graph coloring problems with distance constraints. In Proc. of I Workshop on Distance Geometry and Appl. (DGA 2013).

Karp, R. (1972). Reducibility Among Combinatorial Problems. In Miller, R. E. and Thatcher, J. W., editors, Complexity of Computer Computations, pages 85–103. Plenum Press.

Koster, A. (1999). Frequency assignment: models and algorithms. PhD thesis, Univ. Maastricht.

Mehrotra, A. and Trick, M. (1996). A column generation approach for graph coloring. INFORMS Journal on Computing, 8:344–354.

Méndez-Díaz, I. and Zabala, P. (2006). A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics, 154(5):826–847.