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 grafos y el producto tensorial de grafos . Esta conjetura establece que
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/3/30/Hdetniemi_conjecture_example.svg/300px-Hdetniemi_conjecture_example.svg.png)
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 es de color k , se puede colorear con k G × H usando el mismo color para cada copia de G en el producto; simétricamente si H es de color k . Por lo tanto, la conjetura de Hedetniemi equivale a la afirmación de que los productos tensoriales no se pueden colorear 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.
Casos conocidos
Cualquier gráfico con un conjunto de bordes no vacío requiere al menos dos colores; si G y H no son 1-colorantes, es decir, ambos contienen un borde, entonces su producto también contiene un borde y, por lo tanto, tampoco es 1-colorante. 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 2-coloreables, es decir, no son bipartitos , 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 es 2-colorante. En otras palabras, si G × H es 2-colorante, entonces al menos uno de G y H debe ser 2-colorante también.
El siguiente caso ha sido probado mucho después de la afirmación de la conjetura, por El-Zahar y Sauer (1985) : si el producto G × H es 3-colorante, entonces uno de G o H también debe ser 3-colorante. En particular, la conjetura es cierta siempre que G o H es 4-coloreable (ya que entonces la desigualdad χ ( G × H ) ≤ min {χ ( G ), χ ( H )} solo puede ser estricta cuando G × H es 3- de colores). En los casos restantes, ambos gráficos del producto tensorial son al menos 5-cromáticos y solo se ha avanzado en situaciones muy restringidas.
Conjetura débil de Hedetniemi
La siguiente función (conocida como función Poljak-Rödl ) mide qué tan bajo puede ser el número cromático de productos de n gráficos cromáticos.
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 & 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 por un máximo de 9. Por lo tanto, una prueba de la de Hedetniemi La conjetura para gráficos de 10 cromáticos ya implicaría la Conjetura débil de Hedetniemi para todos los gráficos.
Gráficos multiplicativos
La conjetura se estudia en el contexto más general de homomorfismos de grafos , especialmente debido a las interesantes relaciones con la categoría de grafos (con grafos como objetos y homomorfismos como flechas). Para cualquier gráfico fijo K , se considera gráficos G que admiten un homomorfismo de K , escrito G → K . Estos también se denominan gráficos K -colorables. Esto generaliza la noción habitual de coloración de grafos, ya que de las definiciones se deduce que una coloración k es lo mismo que una coloración K k (un homomorfismo en el grafo completo sobre k vértices).
Una gráfica K se llama multiplicativa si para cualquier gráfica G , H , el hecho de que G × H → K se cumple implica que G → K o H → K se cumple. Al igual que con los colorantes clásicos, la implicación inversa lleva a cabo siempre: si G (o H , simétricamente) es K -colorable, entonces G × H es fácilmente K -colored mediante el uso de los mismos valores independientemente de H . La conjetura de Hedetniemi es equivalente al enunciado de que cada gráfica completa es multiplicativa.
Los casos conocidos anteriores 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 mostrar que todas las gráficas de ciclos son multiplicativas. Más tarde, 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, no se cumplen ni G → H ni H → G ). 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.
Grafo exponencial
Dado que el producto tensor de gráficos es el producto de la categoría-teórico en la categoría de gráficos (con gráficos como objetos y homomorfismos como flechas), la conjetura puede ser reformulada en términos de la siguiente construcción en los gráficos K y G . El gráfico exponencial K G es el gráfico con todas las funciones V (G) → V (K) como vértices (no solo homomorfismos) y dos funciones f , g adyacentes cuando
- f (v) es adyacente a g (v ') en K , para todos los vértices adyacentes v , v' de G .
En particular, hay un bucle en una función f (que es adyacente a sí mismo) si y sólo si la función da un homomorfismo de G a K . Visto de otra manera, hay un borde entre f y g cuando las dos funciones definen un homomorfismo de G × K 2 (el doble cubierta bipartito de G ) a K .
El gráfico exponencial es el objeto exponencial en la categoría de gráficos. Esto significa homomorfismos de G × H a un gráfico K corresponden a homomorfismos de H a K G . Además, hay 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:
- ya sea G o K G es K -colorable, para cada gráfico G .
En otras palabras, la conjetura de Hedetniemi puede verse como un enunciado en gráficas exponenciales: para cada entero k , la gráfica 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 las instancias 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.
Generalizaciones
Generalizada a gráficos dirigidos, la conjetura tiene contraejemplos simples, como lo 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 del tensor tiene exactamente la mitad del número de bordes (para los bordes dirigidos g → g ' en G y h → h' en H , el tensor El producto G × H tiene solo un borde, de (g, h) a (g ', h') , mientras que el producto de los gráficos subyacentes no dirigidos tendría un borde entre (g, h ') y (g', h) también). Sin embargo, la conjetura débil de Hedetniemi resulta ser equivalente en los escenarios dirigidos y no dirigidos ( Tardif y Wehlau 2006 ).
El problema no se puede generalizar a gráficas infinitas: Hajnal (1985) dio un ejemplo de dos gráficas infinitas, cada una de las cuales requiere un número incontable de colores, de modo que su producto puede ser coloreado con muchos colores contables. Rinot (2013) demostró que en el universo construible , por cada infinito cardinal, existen un par de gráficos de número cromático mayor que , de modo que su producto todavía se puede colorear con sólo un número contable de colores.
Problemas relacionados
Sabidussi (1957) demostró una igualdad similar para el producto cartesiano de los gráficos y la redescubrió varias veces después. También se conoce una fórmula exacta para el producto lexicográfico de los gráficos . Duffus, Sands y Woodrow (1985) introdujeron dos conjeturas más fuertes que implican una colorabilidad única.
Referencias
- Fuentes primarias
- Duffus, D .; Sands, B .; Woodrow, RE (1985), "Sobre el número cromático del producto de gráficos", Journal of Graph Theory , 9 (4): 487–495, doi : 10.1002 / jgt.3190090409 , MR 0890239.
- El-Zahar, M .; Sauer, N. (1985), "El número cromático del producto de dos gráficos 4-cromáticos es 4", Combinatorica , 5 (2): 121-126, doi : 10.1007 / BF02579374 , MR 0815577.
- Häggkvist, R .; Hell, P .; Miller, DJ; Neumann Lara, V. (1988), "Sobre las gráficas multiplicativas y la conjetura del producto", Combinatorica , 8 (1): 63–74, doi : 10.1007 / BF02122553 , hdl : 1828/1589 , MR 0951994.
- Hajnal, A. (1985), "El número cromático del producto de dos gráficos cromáticos ℵ 1 puede ser contable", Combinatorica , 5 (2): 137–140, doi : 10.1007 / BF02579376 , MR 0815579.
- Hedetniemi, S. (1966), Homomorfismos de gráficos y autómatas , Informe técnico 03105-44-T, Universidad de Michigan.
- Poljak, S .; Rödl, V. (1981), "Sobre el número arco-cromático de un dígrafo", Journal of Combinatorial Theory, Serie B , 31 (2): 190-198, doi : 10.1016 / S0095-8956 (81) 80024-X.
- Rinot, A. (2013), Conjetura de Hedetniemi para gráficos incontables , arXiv : 1307.6841 , Bibcode : 2013arXiv1307.6841R.
- Sabidussi, G. (1957), "Gráficos con un grupo dado y propiedades teóricas de gráficos dadas", Canadian Journal of Mathematics , 9 : 515–525, doi : 10.4153 / CJM-1957-060-7 , MR 0094810.
- Shitov, Yaroslav (mayo de 2019), contraejemplos de la conjetura de Hedetniemi , arXiv : 1905.02167.
- Tardif, C. (2005), "Gráficos multiplicativos y endomorfismos de semi-celosía en la categoría de gráficos", Journal of Combinatorial Theory, Serie B , 95 (2): 338–345, doi : 10.1016 / j.jctb.2005.06. 002.
- Tardif, C .; Wehlau, D. (2006), "Números cromáticos de productos de gráficos: las versiones dirigida y no dirigida de la función Poljak-Rödl", Journal of Graph Theory , 51 (1): 33–36, doi : 10.1002 / jgt.20117.
- Wrochna, M. (2017), "Las gráficas sin cuadrados son multiplicativas", Journal of Combinatorial Theory, Serie B , 122 : 479–507, arXiv : 1601.04551 , doi : 10.1016 / j.jctb.2016.07.007.
- Encuestas y fuentes secundarias
- Imrich, Wilfried; Klavžar, Sandi (2000), Gráficos de productos: estructura y reconocimiento , Wiley, ISBN 0-471-37039-8.
- Kalai, Gil (10 de mayo de 2019), "Una sensación en las noticias de la mañana - Yaroslav Shitov: contraejemplos a la conjetura de Hedetniemi" , Combinatoria y más.
- Klavžar, Sandi (1996), "Productos de gráficos para colorear: una encuesta", Matemáticas discretas , 155 (1-3): 135-145, doi : 10.1016 / 0012-365X (94) 00377-U , MR 1401366.
- Sauer, N. (2001), "Conjetura de Hedetniemi: una encuesta", Matemáticas discretas , 229 (1-3): 261-292, doi : 10.1016 / S0012-365X (00) 00213-2 , MR 1815610.
- Tardif, Claude (2008), "La conjetura de Hedetniemi, 40 años después" (PDF) , Graph Theory Notes of New York , 54 : 46–57, MR 2445666.
- Zhu, Xuding (1998), "Una encuesta sobre la conjetura de Hedetniemi", Taiwanese J. Math. , 2 (1): 1–24, doi : 10.11650 / twjm / 1500406890 , MR 1609464.
enlaces externos
- Un gran avance en la teoría de grafos , Numberphile