Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420077 | Discrete Applied Mathematics | 2012 | 12 Pages |
A coloring of a graph GG is an assignment of colors to the vertices of GG such that any two vertices receive distinct colors whenever they are adjacent. An acyclic coloring of GG is a coloring such that no cycle of GG receives exactly two colors, and the acyclic chromatic number χA(G)χA(G) of a graph GG is the minimum number of colors in any such coloring of GG. Given a graph GG and an integer kk, determining whether χA(G)≤kχA(G)≤k or not is NP-complete even for k=3k=3. The acyclic coloring problem arises in the context of efficient computations of sparse and symmetric Hessian matrices via substitution methods. In this work we start an integer programming approach for this problem, by introducing a natural integer programming formulation and presenting six families of facet-inducing valid inequalities.