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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.