# Total chromatic number and total clique number

Let $G=(V,E)$ be a finite, simple, unconnected graph. We define the total graph $T(G)$ of $G$ as follows:

• $V(T(G)) = (V\times\{0\}) \cup (E\times\{1\})$,
• $E(T(G)) = E_v \cup E_e \cup E_{v+e}$, where
• $E_v = \big\{\{(v,0), (w,0)\}: \{v,w\}\in E\big\}$,
• $E_e = \big\{\{(e,1), (f,1)\}: (e,f\in E) \land (e\neq f)\land (e\cap f \neq \emptyset\big)\}$, and
• $E_{v+e} = \big\{\{(v,0), (e,1)\}: v\in e\big\}$.

I think that for the clique number we have $\omega(T(G)) = \Delta(G)+1$ (where $\Delta(G)$ is the maximum degree in $G$), except if $\Delta(G) = 1$, but I have to check this (it's probably an easy question).

Question: Is there a $G$ such that $\chi(T(G)) > \omega(T(G))$?

• The total colouring conjecture is that $\chi(T(G)) \leq \Delta(G) + 2$. If there is an example showing that this many colours are needed then your first observation would mean that the answer is yes. – Ben Barber May 26 '16 at 9:41

Counterexamples are, for example, complete graphs with even number $2k$ of vertices. If we manage to color such a graph with $2k$ colors, then all vertices have different colors, and from each vertex of color, say, $s$, there is exactly one edge of each color except $s$. Therefore total number of edges of each color is $(2k-1)/2$, this is not possible.