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

Improve this question
$\endgroup$
1
  • 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$ Commented May 26, 2016 at 9:41

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.