0
$\begingroup$

Consider a complete multipartite graph on $n$ vertices having maximum degree $\Delta$. Then, it is known that the total chromatic number of the graph is $\le\Delta+2$. The proof uses the fact that a maximum independent set has size more than or equal to $n-\Delta-1$.

But, in the classic text by H P Yap,"Total Colourings of Graphs", it is also remarked that the above result follows directly from Tutte's 1-factor theorem. I am unable to prove the same. For, suppose if the graph were having an odd number of vertices, then how could Tutte's theorem help there? If the 1-factor theorem were applied to a subgraph of the graph with an independent set removed, then how would we ensure distinct perfect matchings? Any hints? Thanks beforehand.

$\endgroup$

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.