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.


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.