Let $G=(V,E)$ be a finite, simple, undirected, connected graph, and let $\omega(G)$ denote its clique number. Assume that $G$ has a partition into $m$ independent subsets $U_1,\dots, U_m$ such that for every $i \neq j$ the induced graph $G[U_i \cup U_j]$ is connected. Does this imply that $\omega(G) = m$?
1 Answer
$\begingroup$
$\endgroup$
0
Set $U_i=\{a_{1i},a_{2i},a_{3i}\}$ for $i=1,2,3,4$, and let $a_{ki}$ be connected to $a_{\ell j}$ iff $k\neq \ell$ and $i\neq j$ (in other words, this is the tensor product of $K_3$ and $K_4$). Then all condition are satisfied, but even the chromatic number equals $3$, not $4$.
