0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ben Barber May 26 '16 at 9:41
3
$\begingroup$

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.

$\endgroup$

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.