0
$\begingroup$

Hedetniemi's conjecture is about the chromatic number of the categorical product of simple, finite, undirected graphs $G, H$ : it claims that $\chi(G\times H) = \min \{\chi(G), \chi(H)\}$.

For any simple, undirected graph $G=(V,E)$ we set $\text{col}(G) = \sup\{\delta(H): H\subseteq G\}+1$, where $\delta(\cdot)$ denotes the minimal degree. We have $\chi(G) \leq \text{col}(G)$ for any graph $G$.

Do we have $\text{col}(G\times H) = \min\{\text{col}(G), \text{col}(H)\}$ for all $G, H$?

$\endgroup$

1 Answer 1

3
$\begingroup$

No. If $H=G=K_d$, $\text{col}(G)=d$, but $G\times G$ is a regular graph of degree $(d-1)^2$, thus $\text{col}(G\times G)\geqslant (d-1)^2+1>d$ for $d\geqslant 3$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .