Vertex coloring complete minors

44 Views Asked by At

Say you have a graph G and with a $K_t$ minor. Let H be the smallest subgraph of G that has $K_t$ as a minor (for all $v\in V(H)$, $H\setminus v$ does not contain $K_t$ as a minor). Then we can partition H into sets $V_1, V_2, \ldots V_t$ such that $H\left[V_i\right]$ is connected for all $i\in \{1, 2, \ldots, t\}$. If $\chi(H\left[V_i\right]) < t$ for all $i\in \{1,2,\ldots, t\}$ and the clique number of H is less than t can we say $\chi(H) \leq t$?

1

There are 1 best solutions below

2
On

Isn't any odd cycle other than $K_3$ as $H$ a counterexample already?

$\chi(H)=3$ and $\chi(H[V_i])\le2$ as any proper subgraph of $H$ is just a path.