  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. 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
three families of nontrivial valid inequalities: vertex-clique inequalities
based on standard clique inequalities of the Stable Set Polytope,
congruent-$2k3$ cycle inequalities based on the parity of the vertex set
induced by the cycle, and even-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 vertex-clique and even-cliques are
always facet-defining. Finally, we present preliminary computational results of
a Column Generation algorithm for the Total Coloring Problem and a Cutting
Plane algorithm for the Total Matching Problem.
