Let $G=(V,E)$ be a finite, simple, undirected graph. For any set $X$ we set $[X]^2 := \big\{\{x,y\}: x\neq y \in X\big\}$. If $T$ is a tree, then a map $W: V(T)\to {\cal P}(V(G))$ is called a tree-decomposition if
- $V(G) = \bigcup {\text{im}}(W)$, and $E(G) \subseteq \bigcup\{[W(t)]^2: t\in V(T)\}$, and
- if $t_1, t_2\in V(T)$ and $t$ lies on the path in $T$ between $t_1$ and $t_2$, then $W(t_1)\cap W(t_2) \subseteq W(t)$.
If $T$ is a tree and $W$ is a tree-decomposition, we say that the chromatic number of $W$ is the maximum of $\chi(W(t))$ over all $t \in V(T)$; and $G$ has tree-chromatic number at most $k$ if it admits a tree-decomposition with chromatic number atmost $k$. Let us denote the tree-chromatic number of $G$ by $\Upsilon(G)$.
It is easy to see that $\Upsilon(G) \leq \chi(G)$, and if $K$ is a clique in $G$, we have $|K|\leq \Upsilon(G)$.
Let $\eta(G)$ be the Hadwiger number of $G$, that is the maximum size that a complete minor of $G$ can have.
Is it true that $\Upsilon(G) \leq \eta(G)$ for all finite graphs $G$?
