On a theorem of Chetwynd and Hilton in Graphs

Question

Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its incident vertices receive same colour) with $\Delta+1$ colours. Let the vertices be properly coloured with $\Delta+1$ colours say, $c_i\ \ i\in\{1,2,\ldots,\Delta+1\}$. Let $n_i$ be the number of vertices in the $i$th colour class. In addition, let $r$ be the number of $n_i$ with $n_i\equiv|V(G)|\bmod2$. Then, is it true that $\sum_{v\in V(G)}\Delta-d(v)\ge\Delta-r+1$, where $d(v)$ is the degree of vertex $v$?

I think it is true, but the proof eludes me. Specificaly, there are $r$ and $\Delta-r+1$ colour classes of different parity. But, how does the deficiency between maximum degree and vertex degree and total colourability come into play here? Note that the inequality is strictly not true for graphs which cannot be totally coloured with $\Delta+1$ colours

Answer 1

A graph $G$ is called conformable is there exists a proper vertex coloring using $\Delta + 1$ colors (really at most this many colors as color classes are allowed to be empty) such that $$\sum_{v \in V} (\Delta - d(v)) \geq \Delta - r + 1$$ where $r$ is as defined in the question.

In Lemma 1 of "Non-conformable subgraphs of non-conformable graphs" by Chetwynd and Hilton (which is linked in the comments) it is shown that is $G$ has a total coloring with $\Delta + 1$, then $G$ is conformable. The proof shows that using the proper vertex coloring induced by the total coloring the above inequality is satisfied. Added in edit: Here is a bit of elaboration on the proof of the lemma. Assume $G$ has a total coloring with $\Delta + 1$ colors. Notice for every vertex on degree $\Delta$ each color is used either at the vertex or on an edge incident to it. Let us group the LHS sum over vertices by color class in this total coloring. Take some color $i$ and consider all edges with this color. This gives us a matching in the graph. Think about removing all vertices incident on an edge in this matching. This gives a graph where the size of the vertex set is the same parity as $|V(G)|$. Let $U$ denote the set of vertices remaining. This color class contributes to the RHS when $n_i$ is the opposite parity of $|V(G)|$. If it is the case that $n_i$ differs from $|V(G)|$ in parity then at least one vertex in $U$ must not be in the color class. However, every vertex of maximal degree $\Delta$ left in $U$ must be in the color class. Therefore, where $n_i$ and $|V(G)|$ have opposite parity the color class must contain at least one vertex of degree $< \Delta$ and hence will contribute at least one to the sum on the LHS.

A conformable graph can have proper vertex coloring using $\Delta+1$ colors where the inequality is not satisfied. Consider a cycle of length $6(2k+1)$. This is a $2$-regular graph so $\Delta + 1 = 3$ and the LHS of the inequality is zero. This graph has a total coloring with using $3$ colors and hence is conformable. The total coloring just comes from coloring vertex, edge, vertex, edge, ... with $1,2,3,1,2,3,\dots$ which works because the cycle has length divisible by $3$. However, since the length of the cycle is even, it is bipartite and the proper vertex coloring with $2$ colors will have color class sizes $3(2k+1)$, $3(2k+1)$, and $0$. Which means $r=1$ and the RHS of the inequality is $2$. So, the inequality is not satisfied.

If I understand what is being asked I think this answers the question. Being conformable means there exists some proper vertex coloring with $\Delta+1$ colors satisfying the inequality. However, there can also exist proper vertex colorings with $\Delta+1$ colors not satisfying the inequality.