En teoría de grafos , la conjetura de Hedetniemi , formulada por Stephen T. Hedetniemi en 1966, se refiere a la conexión entre la coloración de gráficos y el producto tensorial de los gráficos . Esta conjetura afirma que
Aquí denota el número cromático de un gráfico finito no dirigido .
La desigualdad χ( G × H ) ≤ min {χ( G ), χ( H )} es fácil: si G tiene k -color, se puede k -colorear G × H usando el mismo color para cada copia de G en el producto; simétricamente si H es k -coloreado. Por tanto, la conjetura de Hedetniemi equivale a la afirmación de que los productos tensoriales no pueden colorearse con un número inesperadamente pequeño de colores.
Yaroslav Shitov (2019) (ver Kalai 2019) descubrió un contraejemplo de la conjetura, refutando así la conjetura en general.
Cualquier gráfico con un conjunto de aristas no vacío requiere al menos dos colores; si G y H no son 1 coloreables, es decir, ambos contienen un borde, entonces su producto también contiene un borde y, por lo tanto, tampoco es 1 coloreable. En particular, la conjetura es cierta cuando G o H es un gráfico bipartito, ya que entonces su número cromático es 1 o 2.
De manera similar, si dos gráficos G y H no son bicolores, es decir, no son bipartitos , entonces ambos contienen un ciclo de longitud impar. Dado que el producto de dos gráficos de ciclos impares contiene un ciclo impar, el producto G × H tampoco se puede colorear en 2 colores. En otras palabras, si G × H tiene dos colores, entonces al menos uno de G y H también debe tener dos colores.
El siguiente caso fue demostrado mucho después del enunciado de la conjetura, por El-Zahar y Sauer (1985): si el producto G × H es tricolorable, entonces uno de G o H también debe ser tricolorable. En particular, la conjetura es cierta siempre que G o H sea 4-coloreable (ya que entonces la desigualdad χ( G × H ) ≤ min {χ( G ), χ( H )} sólo puede ser estricta cuando G × H es 3- de colores). En los casos restantes, ambas gráficas del producto tensorial son al menos 5 cromáticas y sólo se han realizado avances en situaciones muy restringidas.
La siguiente función (conocida como función de Poljak-Rödl ) mide qué tan bajo puede ser el número cromático de productos de n -gráficas cromáticas.
La conjetura de Hedetniemi equivale entonces a decir que f ( n ) = n . En cambio, la conjetura débil de Hedetniemi establece simplemente que la función f ( n ) es ilimitada. En otras palabras, si el producto tensorial de dos gráficos se puede colorear con pocos colores, esto debería implicar algún límite en el número cromático de uno de los factores.
El resultado principal de (Poljak y Rödl 1981), mejorado independientemente por Poljak, James H. Schmerl y Zhu, establece que si la función f ( n ) está acotada, entonces está acotada como máximo por 9. Por tanto, una prueba de la teoría de Hedetniemi La conjetura para gráficos de 10 cromáticos ya implicaría la conjetura de Hedetniemi débil para todos los gráficos.
La conjetura se estudia en el contexto más general de los homomorfismos de grafos , especialmente debido a sus interesantes relaciones con la categoría de grafos (con grafos como objetos y homomorfismos como flechas). Para cualquier gráfico fijo K , se consideran gráficos G que admiten un homomorfismo con K , escrito G → K. Estos también se denominan K -gráficos coloreables. Esto generaliza la noción habitual de coloración de gráficos, ya que de las definiciones se deduce que una k -coloración es lo mismo que una K k -coloración (un homomorfismo en el gráfico completo en k vértices).
Un gráfico K se llama multiplicativo si para cualquier gráfico G , H , el hecho de que G × H → K se cumpla implica que G → K o H → K se cumpla. Al igual que con las coloraciones clásicas, siempre se cumple la implicación inversa: si G (o H , simétricamente) es K -colorable, entonces G × H es fácilmente K -coloreable usando los mismos valores independientemente de H . La conjetura de Hedetniemi es entonces equivalente a la afirmación de que cada gráfico completo es multiplicativo.
Los casos conocidos anteriormente equivalen a decir que K 1 , K 2 y K 3 son multiplicativos. El caso de K 4 está ampliamente abierto. Por otro lado, la prueba de El-Zahar & Sauer (1985) ha sido generalizada por Häggkvist et al. (1988) para demostrar que todas las gráficas de ciclos son multiplicativas. Posteriormente, Tardif (2005) demostró de manera más general que todas las camarillas circulares K n/k con n/k < 4 son multiplicativas. En términos del número cromático circular χ c , esto significa que si χ c ( G × H ) < 4 , entonces χ c ( G × H ) = min { χ c ( G ), χ c ( G )} . Wrochna (2017) ha demostrado que las gráficas sin cuadrados son multiplicativas.
Se pueden construir ejemplos de gráficos no multiplicativos a partir de dos gráficos G y H que no son comparables en el orden de homomorfismo (es decir, ni G → H ni H → G se cumplen). En este caso, dejando K = G × H , trivialmente tenemos G × H → K , pero ni G ni H pueden admitir un homomorfismo en K , ya que compuesto con la proyección K → H o K → G daría una contradicción.
Dado que el producto tensorial de los gráficos es el producto teórico de categorías en la categoría de los gráficos (con los gráficos como objetos y los homomorfismos como flechas), la conjetura se puede reformular en términos de la siguiente construcción sobre los gráficos K y G. La gráfica exponencial K G es la gráfica con todas las funciones V(G) → V(K) como vértices (no solo homomorfismos) y dos funciones f , g adyacentes cuando
En particular, hay un bucle en una función f (es adyacente a sí misma) si y sólo si la función da un homomorfismo de G a K. Visto de otra manera, hay una ventaja entre f y g siempre que las dos funciones definen un homomorfismo de G × K 2 (la doble cobertura bipartita de G ) a K.
La gráfica exponencial es el objeto exponencial en la categoría de gráficas. Esto significa que los homomorfismos de G × H a un gráfico K corresponden a homomorfismos de H a K G. Además, existe un homomorfismo eval : G × K G → K dado por eval( v , f ) = f ( v ) . Estas propiedades permiten concluir que la multiplicatividad de K es equivalente (El-Zahar & Sauer 1985) al enunciado:
En otras palabras, la conjetura de Hedetniemi puede verse como una afirmación sobre gráficos exponenciales: para cada número entero k , el gráfico K k G es k -colorable o contiene un bucle (lo que significa que G es k -colorable). También se pueden ver los homomorfismos eval : G × K k G → K k como los casos más difíciles de la conjetura de Hedetniemi: si el producto G × H fuera un contraejemplo, entonces G × K k G también sería un contraejemplo.
Generalizada a gráficos dirigidos, la conjetura tiene contraejemplos simples, como observaron Poljak y Rödl (1981). Aquí, el número cromático de un gráfico dirigido es solo el número cromático del gráfico subyacente, pero el producto tensorial tiene exactamente la mitad del número de aristas (para aristas dirigidas g→g' en G y h→h' en H , el tensor el producto G × H tiene solo una arista, de (g,h) a (g',h') , mientras que el producto de los gráficos no dirigidos subyacentes tendría una arista entre (g,h') y (g',h) también). Sin embargo, la conjetura de Hedetniemi débil resulta ser equivalente en entornos dirigidos y no dirigidos (Tardif y Wehlau 2006).
El problema no se puede generalizar a gráficos infinitos: Hajnal (1985) dio un ejemplo de dos gráficos infinitos, cada uno de los cuales requiere un número incontable de colores, de modo que su producto puede colorearse con sólo un número contable de colores. Rinot (2013) demostró que en el universo construible , para cada cardinal infinito , existe un par de gráficos de número cromático mayor que , de modo que su producto aún puede colorearse con solo un número contable de colores.
Sabidussi (1957) demostró una igualdad similar para el producto cartesiano de gráficos y la redescubrió varias veces después. También se conoce una fórmula exacta para el producto lexicográfico de grafos . Duffus, Sands y Woodrow (1985) introdujeron dos conjeturas más sólidas sobre la colorabilidad única.
