Facets based on cycles and cliques for the acyclic coloring polytope

Braga, Mónica; Marenco, Javier

RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 6, pp. 1863-1874.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

A coloring of a graph is an assignment of colors to its vertices such that any two vertices receive distinct colors whenever they are adjacent. An acyclic coloring is a coloring such that no cycle receives exactly two colors, and the acyclic chromatic number χ$$(G) of a graph G is the minimum number of colors in any such coloring of G. Given a graph G and an integer k, determining whether χ$$(G) ≤ k or not is NP-complete even for k = 3. The acyclic coloring problem arises in the context of efficient computations of sparse and symmetric Hessian matrices via substitution methods. In a previous work we presented facet-inducing families of valid inequalities based on induced even cycles for the polytope associated to an integer programming formulation of the acyclic coloring problem. In this work we continue with this study by introducing new families of facet-inducing inequalities based on combinations of even cycles and cliques.

[1] E. Balas, S. Ceria and G. Cornuéjols, Lift-and-project cutting plane algorithm for mixed $0–1$ Programs, Math. Program. 58 (1993) 295–324. | DOI | MR | Zbl

[2] O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211–236. | DOI | MR | Zbl

[3] O.V. Borodin, A.V. Kostochka, A. Raspaud and E. Sopena, Acyclic colouring of $1$-planar graphs, Discrete Appl. Math. 114 (2001) 29–41. | DOI | MR | Zbl

[4] M. Braga and J. Marenco, Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope, RAIRO: OR 50 (2016) 627–644. | DOI | Numdam | MR | Zbl

[5] M. Braga, D. Delle Donne and J. Marenco, A polyhedral study of the acyclic coloring problem, Discrete Appl. Math. 160 (2012) 2606–2617. | DOI | MR | Zbl

[6] T.F. Coleman and J. Cai, The cyclic coloring problem and estimation of sparse Hessian matrices, SIAM J. Alg. Disc. Meth. 7 (1986) 221–235. | DOI | MR | Zbl

[7] T.F. Coleman and J.J. Moré, Estimation of sparse Jacobian matrices and graph coloring problems, SIAM J. Numer. Anal. 20 (1983) 187–209. | DOI | MR | Zbl

[8] G. Fertin and A. Raspaud, Acyclic coloring of graphs of maximum degree five: nine colors are enough, Inf. Process. Lett. 105 (2008) 65–72. | DOI | MR | Zbl

[9] A.H. Gebremedhin, F. Manne and A. Pothen, What color is your Jacobian? Graph coloring for computing derivatives, SIAM Rev. 47 (2005) 629–705. | DOI | MR | Zbl

[10] A.H. Gebremedhin, A. Tarafdar, F. Manne and A. Pothen, New acyclic and star coloring algorithms with application to computing hessians, SIAM J. Sci. Comput. 29 (2007) 1042–1072. | DOI | MR | Zbl

[11] A.H. Gebremedhin, A. Tarafdar, A. Pothen and A. Walther, Efficient computation of sparse hessians using coloring and automatic differentiation, INFORMS J. Comput. 21 (2009) 209–223. | DOI | MR | Zbl

[12] A.V. Kostochka, Upper bounds of chromatic functions of graphs (in Russian), Ph.D. thesis, University of Novosibirsk, Russia (1978).

[13] I. Méndez-Daz and P. Zabala, A branch-and-cut algorithm for graph coloring, Discrete Appl. Math. 154 (2006) 826–847. | DOI | MR | Zbl

[14] I. Méndez-Daz and P. Zabala, A cutting plane algorithm for graph coloring, Discrete Appl. Math. 156 (2008) 159–179. | DOI | MR | Zbl