En esta pregunta, un grafo es un grafo finito, no dirigido, sin bucles o aristas múltiples, y un coloreado de un grafo es un coloreado de vértices adecuado. El producto $G \times H$ de los grafos $G$ y $H$ es el grafo cuyo conjunto de vértices es el producto de los conjuntos de vértices de $G$ y $H$ y cuyo conjunto de aristas es el producto de los conjuntos de aristas de $G$ y $H$, con la relación de incidencia obvia.
Sean $G$ y $H$ grafos. Cualquier coloreado de $n$ colores de $G$ da lugar a un coloreado de $n$ colores de $G \times H$: simplemente pinte $(x, y)$ del mismo color que $x$. (O, si lo prefiere, un coloreado de $n$ colores de un grafo es simplemente un homomorfismo en el grafo completo $K_n$, por lo que podemos componer el coloreado $G \to K_n$ con la proyección $G \times H \to G$ para obtener un coloreado $G \times H \to K_n$). De manera similar, cualquier coloreado de $n$ colores de $H$ da lugar a un coloreado de $n$ colores de $G \times H. Digamos que un coloreado de $G \times H$ que surge de una de estas dos formas es obtenido por proyección.
El párrafo anterior deja en claro que $\chi(G \times H) \leq \min\{ \chi(G), \chi(H) \}$, donde $\chi$ significa número cromático. La conjetura de Hedetniemi establece que esta es una igualdad. En otras palabras, dice que no hay coloreados de un producto más económicos que aquellos obtenidos por proyección. Mi pregunta:
Sean $G$ y $H$ grafos. ¿Está cada coloreado de $G \times H$ con $\chi(G \times H)$ colores obtenido por proyección?
No se puede saber a ciencia cierta que la respuesta sea sí, a menos que me haya perdido alguna noticia, ya que eso implicaría la conjetura de Hedetniemi. Pero tal vez la respuesta sea no, o tal vez se sepa que esta conjetura aparentemente más fuerte en realidad se deduciría de la conjetura original de Hedetniemi.
Editar Suponga que los grafos están conectados, de lo contrario, la respuesta es trivialmente no. (Por ejemplo, considere $(K_2 \sqcup K_2) \times K_2$).
