Hedetniemi's Conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For finite simple graphs $G,H$, the tensor product $G\times H$ has vertices $(g,h)$ and joins $(g,h)$ to $(g',h')$ exactly when $gg'\in E(G)$ and $hh'\in E(H)$. Write $G\to H$ for a graph homomorphism. For $n\ge2k>0$, let $K_{n/k}$ have vertices $\mathbb Z/n\mathbb Z$, with distinct vertices adjacent when their cyclic distance is at least $k$; define $\chi_c(G)=\inf\{n/k:G\to K_{n/k}\}$ for graphs with an edge, and $\chi_c(G)=1$ for nonempty edgeless graphs. The exponential graph $K_n^G$ has as vertices all maps $V(G)\to V(K_n)$, with $f,f'$ adjacent when $f(x)f'(y)\in E(K_n)$ for every ordered pair $(x,y)$ with $xy\in E(G)$. A graph $K$ is multiplicative if $G\times H\to K$ always implies $G\to K$ or $H\to K$.

Statement recorded in the supplied source.

The recorded conjecture is \[\chi(G\times H)=\min\{\chi(G),\chi(H)\}.\] Equivalently, whenever $\chi(G)>n$, must $K_n^G$ be $n$-colorable? The source also records Zhu's stronger circular version \[\chi_c(G\times H)=\min\{\chi_c(G),\chi_c(H)\},\] equivalently multiplicativity of every circular complete graph $K_{n/k}$. It additionally defines $f(n)=\min\{\chi(G\times H):\chi(G)=\chi(H)=n\}$, so the original equality is $f(n)=n$. [S2]

Short English statement

Does the tensor product preserve the smaller chromatic number? The source also asks the circular-coloring version and its equivalent homomorphism formulations.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3233 (OPG-806). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Hedetniemi's Conjecture, original node 806, statement and mathematical discussion. https://www.openproblemgarden.org/op/hedetniemis_conjecture.