Total chromatic number and total clique number

Question

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))$?

Answer 1

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.

Your observation on clique number is correct: each clique either contains at least two edges and at most one vertex, or it contains unique edge and at most 2 vertices, or it contains only vertices. All cases are clear.