Total Coloring and Total Matching: Polyhedra and Facets

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 different colors. 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 the Weighted Total Matching Problem. Hence, we study the Total Matching Polytope. We introduce two families of nontrivial valid inequalities: congruent-2k3 cycle inequalities based on the parity of the vertex set induced by the cycle, and clique inequalities induced by complete subgraphs of even order. We prove that congruent-2k3 cycle inequalities are facet-defining only when k = 4, while the even cliques are always facet-defining. 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.