A total coloring of a graph G = (V, E) is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the end-points and the edge itself receive a different color. Any valid total coloring induces a partition of the elements of G into total matchings, which are defined as subsets of vertices and edges that can take the same color. In this paper, we propose Integer Linear Programming models for both the Total Coloring and the Total Matching problems, and we study the strength of the corresponding Linear Programming relaxations. The total coloring is formulated as the problem of finding the minimum number of total matchings that cover all the graph elements, and we prove that this relaxation is tighter than a natural assignment model. This covering formulation can be solved by a column generation algorithm, where the pricing subproblem corresponds to a Weighted Total Matching Problem. Hence, we study the Total Matching Polytope, and we introduce two families of nontrivial facet-defining inequalities: cycle inequalities based on the parity of the vertex set induced by the cycle, and clique inequalities induced by complete subgraphs of even order. Since the separation problem of the clique inequalities of even order is NP-hard, we get a polyhedral proof of the NP-hardness of the Weighted Total Matching Problem.
Citation
University of Pavia