Consider the total graph of a regular graph. From the structure, it seems that it has a similar structure to the line graph ( two different sub-cliques joining at a single point) except that, in addition, there is an edge between two different sub-cliques. Note that the sub-cliques in the total graph are the just the sub-cliques which are present in the line graph of the graph with a vertex added to each sub-clique make it adjacent to all the vertices of a particular sub-clique, thereby increasing the order of the sub-cliques by one. This means that the clique number of the total graph of a graph is one more than the clique number of the line graph of the same graph.

This leads me to infer that the total graph of a graph has similar chromatic properties as a line graph of a graph. Specifically, I expect the total graph of a graph to satisfy a similar bound to Vizing's theorem for line graphs. Will this be true? Thanks beforehand.


1 Answer 1


It depends on what you mean by "similar". It's known that $χ(T) ≤ Δ(G) + 10^{26}$, where $T$ is the total graph of $G$. As the graph $C_4$ have $Δ=2$ and $χ(T)=4$, it follows that the constant term is at least $2$. The Total coloring conjecture states that this is exactly the case, i.e. $χ(T) ≤ Δ(G) + 2$.

  • $\begingroup$ yes, that is what I am pointing at. So is there a way to prove the total coloring conjecture using the structure of line graphs? $\endgroup$
    – vidyarthi
    Aug 22, 2019 at 7:22
  • 3
    $\begingroup$ Well, the problem is open. $\endgroup$ Aug 22, 2019 at 7:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.