Consider a regular graph of order $n$ and degree $\Delta$. Now, by Brooks' theorem, we can partition the vertices into $\Delta+1$ independent sets. The extreme case of $n$ independent sets is only for complete graphs and would be a degenerate case. Now, to perform total coloring, we need to partition the edge sets independently of the vertices. Now, this is accomplished by expanding the already partitioned set of vertices by adding disjoint edge elements which are in turn disjoint from the vertices. After adding the maximum possible number of such edge elements, we partition the remaining edge elements into independent sets. Now, if we are able to prove that the sum total of the totally indepndent sets is less than $\Delta+2$, the total coloring conjecture is proved.

Can we use the fact that when we partition the edge elements, we are actually forming disjoint pair of all the vertices such that sum of such pairs is $n\frac{\Delta}{2}$ in the above construction of total independent sets? Maybe this would help simplify the construction. Any light on this approach? 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.