Skip to main content
1 of 2

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 for $G \cong K_2$, 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))$?