If $G, H$ are finite, simple, undirected graphs, their categorical product $G\times H$ is defined by $V(G\times H) = V(G)\times V(H)$ and $$E(G\times H) = \big\{\{(v_1, w_1),(v_2,w_2)\}: v_i \in V(G)\land w_i\in V(H) \land \{v_1, v_2\} \in E(G) \land \{w_1,w_2\}\in E(H)\big\}.$$

A graph is said to be critical if removing any vertex reduces its chromatic number.

Hedetniemi's conjecture states that $\chi(G\times H) = \min\{\chi(G),\chi(H)\}$ for all finite simple undirected graphs $G,H$.

It implies that the categorical product of critical graphs is also critical. But can we prove this without using Hedetniemi's conjecture?


It doesn't imply that the categorical product of critical graphs is critical, and this is not true. For instance, the complete graph on three vertices, $K_3$, is 3-critical, but $K_3 \times K_3$ is not since it is not just an odd cycle (which is the only type of 3-critical graph).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.