Conjetura de Hadwiger (teoría de grafos)

Generalización no probada del teorema de los cuatro colores.

Problema no resuelto en matemáticas :

¿Todo gráfico con número cromático tiene un gráfico completo de vértice como menor ? ${\displaystyle k}$ ${\displaystyle k}$

(más problemas sin resolver en matemáticas)

Un gráfico que requiere cuatro colores de cualquier color y cuatro subgrafos conectados que, cuando se contraen, forman un gráfico completo, que ilustra el caso k  = 4 de la conjetura de Hadwiger.

En teoría de grafos , la conjetura de Hadwiger establece que si no tiene bucles y no tiene menor , entonces su número cromático satisface . Se sabe que es cierto para . La conjetura es una generalización del teorema de los cuatro colores y se considera uno de los problemas abiertos más importantes y desafiantes en este campo. ${\displaystyle G}$ ${\displaystyle K_{t}}$ ${\displaystyle \chi (G)<t}$ ${\displaystyle 1\leq t\leq 6}$

Con más detalle, si todas las coloraciones adecuadas de un gráfico no dirigido usan o más colores, entonces se pueden encontrar subgrafos conectados disjuntos de modo que cada subgrafo esté conectado por un borde entre sí. Contraer los bordes dentro de cada uno de estos subgrafos para que cada subgrafo colapse en un solo vértice produce un gráfico completo en los vértices como menor de . ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle K_{k}}$ ${\displaystyle k}$ ${\displaystyle G}$

Esta conjetura, una generalización de gran alcance del problema de los cuatro colores , fue formulada por Hugo Hadwiger en 1943 y aún no está resuelta. ^[1] Bollobás, Catlin y Erdős (1980) lo llaman "uno de los problemas sin resolver más profundos de la teoría de grafos". ^[2]

Formas equivalentes

Una forma equivalente de la conjetura de Hadwiger (la contrapositiva de la forma indicada anteriormente) es que, si no hay una secuencia de contracciones de aristas (cada una de las cuales fusiona los dos puntos finales de alguna arista en un solo supervértice) que lleve un gráfico al gráfico completo , entonces debe tener un vértice coloreado con colores. ${\displaystyle G}$ ${\displaystyle K_{k}}$ ${\displaystyle G}$ ${\displaystyle k-1}$

En una coloración mínima de cualquier gráfico , al contraer cada clase de color de la coloración a un solo vértice se producirá un gráfico completo . Sin embargo, este proceso de contracción no produce un menor de porque no hay (por definición) ningún borde entre dos vértices cualesquiera en la misma clase de color, por lo que la contracción no es una contracción de borde (que es necesaria para los menores). La conjetura de Hadwiger establece que existe una forma diferente de contraer adecuadamente conjuntos de vértices en vértices individuales, produciendo un gráfico completo , de tal manera que todos los conjuntos contraídos estén conectados. ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle K_{k}}$ ${\displaystyle G}$ ${\displaystyle K_{k}}$

Si denota la familia de gráficos que tienen la propiedad de que todos los menores de los gráficos pueden ser coloreados, entonces del teorema de Robertson-Seymour se deduce que se puede caracterizar por un conjunto finito de menores prohibidos . La conjetura de Hadwiger es que este conjunto consta de un único menor prohibido, . ${\displaystyle {\mathcal {F}}_{k}}$ ${\displaystyle {\mathcal {F}}_{k}}$ ${\displaystyle (k-1)}$ ${\displaystyle {\mathcal {F}}_{k}}$ ${\displaystyle K_{k}}$

El número de Hadwiger de un gráfico es el tamaño del gráfico completo más grande que es menor de (o de manera equivalente se puede obtener contrayendo los bordes de ). También se conoce como número de camarilla de contracción de . ^[2] La conjetura de Hadwiger se puede expresar en la forma algebraica simple donde denota el número cromático de . ${\displaystyle h(G)}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle K_{k}}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \chi (G)\leq h(G)}$ ${\displaystyle \chi (G)}$ ${\displaystyle G}$

Casos especiales y resultados parciales.

El caso es trivial: un gráfico requiere más de un color si y sólo si tiene una arista, y esa arista es en sí misma menor. El caso también es sencillo: los gráficos que requieren tres colores son los gráficos no bipartitos , y cada gráfico no bipartito tiene un ciclo impar , que puede contraerse a un ciclo de 3, es decir, a un ciclo menor. ${\displaystyle k=2}$ ${\displaystyle K_{2}}$ ${\displaystyle k=3}$ ${\displaystyle K_{3}}$

En el mismo artículo en el que presentó la conjetura, Hadwiger demostró su verdad . ${\displaystyle k=4}$Las gráficas sin menor son las gráficas en series-paralelas y sus subgrafías. Cada gráfico de este tipo tiene un vértice con como máximo dos aristas incidentes; se pueden colorear 3 colores en cualquier gráfico eliminando uno de esos vértices, coloreando el gráfico restante de forma recursiva y luego volviendo a agregar y coloreando el vértice eliminado. Debido a que el vértice eliminado tiene como máximo dos aristas, uno de los tres colores siempre estará disponible para colorearlo cuando se vuelva a agregar el vértice. ${\displaystyle K_{4}}$

La verdad de la conjetura para implica el teorema de los cuatro colores : porque, si la conjetura es verdadera, cada gráfico que requiera cinco o más colores tendría un menor y (según el teorema de Wagner ) sería no plano.Klaus Wagner demostró en 1937 que el caso es en realidad equivalente al teorema de los cuatro colores y, por lo tanto, ahora sabemos que es cierto. Como demostró Wagner, cada gráfico que no tiene menor se puede descomponer mediante sumas de camarillas en piezas que son planas o una escalera de Möbius de 8 vértices , y cada una de estas piezas puede tener 4 colores independientemente una de otra, por lo que las 4- La colorabilidad de un gráfico sin menores se deriva de la colorabilidad de 4 de cada una de las piezas planas. ${\displaystyle k=5}$ ${\displaystyle K_{5}}$ ${\displaystyle k=5}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{5}}$

Robertson, Seymour y Thomas (1993) demostraron la conjetura de , ${\displaystyle k=6}$ utilizando también el teorema de los cuatro colores; Su artículo con esta prueba ganó el Premio Fulkerson de 1994 . De su prueba se desprende que los gráficos integrables sin enlaces , un análogo tridimensional de los gráficos planos, tienen un número cromático como máximo de cinco. ^[3] Debido a este resultado, se sabe que la conjetura es cierta para , ${\displaystyle k\leq 6}$ pero permanece sin resolver para todos . ${\displaystyle k>6}$

Para , se conocen algunos resultados parciales: cada gráfico de 7 cromáticos debe contener un menor o tanto un menor como un menor. ^[4] ${\displaystyle k=7}$ ${\displaystyle K_{7}}$ ${\displaystyle K_{4,4}}$ ${\displaystyle K_{3,5}}$

Cada gráfico tiene un vértice con como máximo aristas incidentes, ^[5] de lo cual se deduce que un algoritmo de coloración voraz que elimina este vértice de bajo grado, colorea el gráfico restante y luego vuelve a agregar el vértice eliminado y lo colorea, coloreará el gráfico dado con colores. ${\displaystyle G}$ ${\textstyle O{\bigl (}h(G){\sqrt {\log h(G)}}{\bigr )}}$ ${\textstyle O{\bigl (}h(G){\sqrt {\log h(G)}}{\bigr )}}$

En la década de 1980, Alexander V. Kostochka ^[6] y Andrew Thomason ^[7] demostraron de forma independiente que todo gráfico sin menor tiene grado promedio y, por lo tanto, puede colorearse usando colores. Una secuencia de mejoras a este límite ha llevado a una prueba de colorabilidad para gráficos sin menores. ^[8] ${\displaystyle K_{k}}$ ${\textstyle O(k{\sqrt {\log k}})}$ ${\textstyle O(k{\sqrt {\log k}})}$ ${\displaystyle O(k\log \log k)}$ ${\displaystyle K_{k}}$

Generalizaciones

György Hajós conjeturó que la conjetura de Hadwiger podría reforzarse a subdivisiones en lugar de menores: es decir, que todo gráfico con número cromático contiene una subdivisión de un gráfico completo . La conjetura de Hajós es cierta para , pero Catlin (1979) encontró contraejemplos a esta conjetura reforzada para ; los casos y permanecen abiertos. ^[9] Erdős y Fajtlowicz (1981) observaron que la conjetura de Hajós falla gravemente para gráficos aleatorios : para cualquiera , en el límite cuando el número de vértices, llega al infinito, la probabilidad se acerca a uno de que un gráfico de vértices aleatorios tenga un número cromático. , y que su subdivisión de camarilla más grande tiene vértices. En este contexto, vale la pena señalar que la probabilidad también se acerca a uno de que un gráfico de vértice aleatorio tenga un número de Hadwiger mayor o igual a su número cromático, por lo que la conjetura de Hadwiger es válida para gráficos aleatorios con alta probabilidad; más precisamente, el número de Hadwiger es con alta probabilidad proporcional a . ^[2] ${\displaystyle k}$ ${\displaystyle K_{k}}$ ${\displaystyle k\leq 4}$ ${\displaystyle k\geq 7}$ ${\displaystyle k=5}$ ${\displaystyle k=6}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \geq ({\tfrac {1}{2}}-\varepsilon )n/\log _{2}n}$ ${\textstyle O({\sqrt {n}})}$ ${\displaystyle n}$ ${\textstyle n/{\sqrt {\log n}}}$

Borowiecki (1993) preguntó si la conjetura de Hadwiger podría ampliarse para incluir la coloración de listas . Para , ${\displaystyle k\leq 4}$ cada gráfico con un número cromático de lista tiene una camarilla menor de vértice . Sin embargo, el número cromático de lista máximo de gráficos planos es 5, no 4, por lo que la extensión ya falla para gráficos libres menores . ^[10] De manera más general, para cada , existen gráficos cuyo número de Hadwiger es y cuyo número cromático de lista es . ^[11] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle K_{5}}$ ${\displaystyle t\geq 1}$ ${\displaystyle 3t+1}$ ${\displaystyle 4t+1}$

Gerards y Seymour conjeturaron que todo gráfico con número cromático tiene un gráfico completo como menor impar . Tal estructura se puede representar como una familia de subárboles separados por vértices de , cada uno de los cuales es de dos colores, de modo que cada par de subárboles está conectado por un borde monocromático. Aunque los gráficos sin menores impares no son necesariamente escasos , se les aplica un límite superior similar al de la conjetura estándar de Hadwiger: un gráfico sin menores impares tiene número cromático . ^[12] ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle K_{k}}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle K_{k}}$ ${\displaystyle K_{k}}$ ${\textstyle \chi (G)=O{\bigl (}k{\sqrt {\log k}}{\bigr )}}$

Imponiendo condiciones adicionales a , puede ser posible probar la existencia de menores mayores que . Un ejemplo es el teorema de snark , que cada gráfico cúbico que requiere cuatro colores en cualquier coloración de borde tiene el gráfico de Petersen como menor, conjeturado por WT Tutte y anunciado para ser demostrado en 2001 por Robertson, Sanders, Seymour y Thomas. ^[13] ${\displaystyle G}$ ${\displaystyle K_{k}}$

Notas

1. Diéstel (2017).
2. Bollobás, Catlin y Erdős (1980).
3. Nešetřil y Thomas (1985).
4. Ken-ichi Kawarabayashi demostró la existencia de a o menor , y Kawarabayashi & Toft (2005) demostraron la existencia de a o menor. ${\displaystyle K_{7}}$ ${\displaystyle K_{3,5}}$ ${\displaystyle K_{7}}$ ${\displaystyle K_{4,4}}$
5. Kostochka (1984). La letra de esta expresión invoca la notación O grande . ${\displaystyle O}$
6. Kostochka (1984).
7. Thomason (1984).
8. Delcourt y Postle (2021); Norin, Postle y canción (2023)
9. Yu y Zickfeld (2006).
10. Voigt (1993); Thomassen (1994).
11. Barát, Joret y Wood (2011).
12. Geelen y col. (2006); Kawarabayashi (2009).
13. Pegg (2002).

Referencias

• Barát, János; Joret, Gwenaël; Wood, David R. (2011), "Refutación de la lista de conjetura de Hadwiger", Electronic Journal of Combinatorics , 18 (1): P232, arXiv : 1110.2272 , doi : 10.37236/719, S2CID  13822279
• Bollobás, B. ; Catlin, Pensilvania; Erdős, Paul (1980), "La conjetura de Hadwiger es cierta para casi todos los gráficos" (PDF) , European Journal of Combinatorics , 1 (3): 195–199, doi : 10.1016/s0195-6698(80)80001-1
• Borowiecki, Mieczyslaw (1993), "Problema de investigación 172", Matemáticas discretas , 121 (1–3): 235–236, doi : 10.1016/0012-365X(93)90557-A
• Catlin, PA (1979), "Conjetura de coloración de gráficos de Hajós: variaciones y contraejemplos", Journal of Combinatorial Theory, Serie B , 26 (2): 268–274, doi : 10.1016/0095-8956(79)90062-5
• Delcourt, Michelle; Postle, Luke (2021), Reducción de la conjetura lineal de Hadwiger para colorear gráficos pequeños , arXiv : 2108.01633
• Diestel, Reinhard (2017), "7.3 Conjetura de Hadwiger", Teoría de grafos , Textos de Posgrado en Matemáticas, vol. 173 (5ª ed.), Springer, Berlín, págs. 183–186, ISBN 978-3-662-57560-4, señor  3822066
• Erdős, Paul ; Fajtlowicz, Siemion (1981), "Sobre la conjetura de Hajós", Combinatorica , 1 (2): 141–143, doi :10.1007/BF02579269, S2CID  1266711
• Geelen, Jim ; Gerards, Bert; Caña, Bruce ; Seymour, Pablo ; Vetta, Adrian (2006), "Sobre la variante menor impar de la conjetura de Hadwiger", Journal of Combinatorial Theory, Serie B , 99 (1): 20–29, doi :10.1016/j.jctb.2008.03.006
• Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckkomplexe", Vierteljschr. Naturalmente. Ges. Zúrich , 88 : 133-143
• Kawarabayashi, Ken-ichi (2009), "Nota sobre cómo colorear gráficos sin K _k -menores impares ", Journal of Combinatorial Theory , Serie B, 99 (4): 728–731, doi : 10.1016/j.jctb.2008.12. 001 , señor  2518204
• Kawarabayashi, Ken-ichi ; Toft, Bjarne (2005), "Cualquier gráfico de 7 cromáticos tiene K ₇ o K _4,4 como menor", Combinatorica , 25 (3): 327–353, doi :10.1007/s00493-005-0019-1, S2CID  41451753
• Kostochka, AV (1984), "Límite inferior del número de gráficos de Hadwiger por su grado promedio", Combinatorica , 4 (4): 307–316, doi :10.1007/BF02579141, MR  0779891, S2CID  15736799
• Nešetřil, Jaroslav ; Thomas, Robin (1985), "Una nota sobre la representación espacial de gráficos", Commentationes Mathematicae Universitatis Carolinae , 26 (4): 655–659, hdl :10338.dmlcz/106404, MR  0831801
• Norin, Sergey; Postle, Lucas; Song, Zi-Xia (2023), "Rompiendo la barrera de la degeneración para colorear gráficos sin menores", Avances en Matemáticas , 422 , artículo n.º 109020, 23 páginas, arXiv : 1910.09378 , doi :10.1016/j.aim.2023.109020, MR  4576840 ${\displaystyle K_{t}}$
• Pegg, Ed, Jr. (2002), "Reseña del libro: El colosal libro de las matemáticas" (PDF) , Avisos de la Sociedad Estadounidense de Matemáticas , 49 (9): 1084–1086{{citation}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
• Robertson, Neil ; Seymour, Pablo ; Thomas, Robin (1993), "Conjetura de Hadwiger para gráficos libres de K6" (PDF) , Combinatorica , 13 (3): 279–361, doi :10.1007/BF01202354, MR  1238823, S2CID  9608738
• Thomason, Andrew (1984), "Una función extrema para contracciones de gráficos", Mathematical Proceedings of the Cambridge Philosophical Society , 95 (2): 261–265, doi :10.1017/S0305004100061521, MR  0735367, S2CID  124801301
• Thomassen, Carsten (1994), "Cada gráfico plano se puede elegir entre cinco opciones", Journal of Combinatorial Theory , Serie B, 62 (1): 180–181, doi : 10.1006/jctb.1994.1062 , MR  1290638
• Voigt, Margit (1993), "Lista de colores de gráficos planos", Matemáticas discretas , 120 (1–3): 215–219, doi : 10.1016/0012-365X(93)90579-I , MR  1235909
• Wagner, Klaus (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen , 114 : 570–590, doi :10.1007/BF01594196, S2CID  123534907
• Yu, Xingxing; Zickfeld, Florian (2006), "Reducción de la conjetura de los 4 colores de Hajós a gráficos de 4 colores", Journal of Combinatorial Theory, Serie B , 96 (4): 482–492, doi : 10.1016/j.jctb.2005.10.001 , señor  2232386