Conjetura de Hadwiger (teoría de grafos)

Generalización no demostrada del teorema de los cuatro colores

Problema sin resolver en matemáticas :

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

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

Un gráfico que requiere cuatro colores en cualquier coloración y cuatro subgrafos conectados que, cuando se contraen, forman un gráfico completo, ilustrando 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 menores , entonces su número cromático satisface . Se sabe que es verdadera 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 el campo. ${\displaystyle G}$ ${\displaystyle K_{t}}$ ${\displaystyle \chi (G)<t}$ ${\displaystyle 1\leq t\leq 6}$

En más detalle, si todas las coloraciones propias de un grafo no dirigido utilizan o más colores, entonces se pueden encontrar subgrafos disjuntos y conexos de tal manera que cada subgrafo esté conectado por una arista a cada uno de los otros subgrafos. Al contraer las aristas dentro de cada uno de estos subgrafos de modo que cada subgrafo colapse en un único vértice se produce un grafo completo en vértices como un menor de . ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle K_{k}}$ ${\displaystyle k}$ ${\displaystyle G}$

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

Formas equivalentes

Una forma equivalente de la conjetura de Hadwiger (la contrapositiva de la forma establecida anteriormente) es que, si no hay una secuencia de contracciones de aristas (cada una fusionando los dos puntos finales de alguna arista en un único supervértice) que lleve un grafo al grafo completo , entonces debe tener una coloración de vértices con colores. ${\displaystyle G}$ ${\displaystyle K_{k}}$ ${\displaystyle G}$ ${\displaystyle k-1}$

En una coloración mínima de cualquier grafo , contraer cada clase de color de la coloración a un único vértice producirá un grafo completo . Sin embargo, este proceso de contracción no produce un menor de porque no hay (por definición) ninguna arista entre dos vértices en la misma clase de color, por lo tanto, la contracción no es una contracción de aristas (que es necesaria para los menores). La conjetura de Hadwiger establece que existe una forma diferente de contraer adecuadamente las aristas de conjuntos de vértices a vértices individuales, produciendo un grafo 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 grafos que tienen la propiedad de que todos los menores de grafos en pueden ser coloreados, entonces se deduce del teorema de Robertson-Seymour que puede caracterizarse por un conjunto finito de menores prohibidos . La conjetura de Hadwiger es que este conjunto consiste en 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 grafo es el tamaño del grafo completo más grande que es menor de (o equivalentemente se puede obtener contrayendo las aristas de ). También se lo conoce como el número de camarilla de contracción de . ^[2] La conjetura de Hadwiger se puede formular 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 grafo requiere más de un color si y solo si tiene una arista, y esa arista es en sí misma un menor. El caso también es fácil: los grafos que requieren tres colores son los grafos no bipartitos , y cada grafo no bipartito tiene un ciclo impar , que puede contraerse a un 3-ciclo, es decir, un menor. ${\displaystyle k=2}$ ${\displaystyle K_{2}}$ ${\displaystyle k=3}$ ${\displaystyle K_{3}}$

En el mismo artículo en el que introdujo la conjetura, Hadwiger demostró su veracidad para . ${\displaystyle k=4}$ Los grafos sin menor son los grafos serie-paralelos y sus subgrafos. Cada grafo de este tipo tiene un vértice con dos aristas incidentes como máximo; se puede aplicar 3 colores a cualquier grafo de este tipo eliminando uno de esos vértices, coloreando el grafo 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 grafo que requiera cinco o más colores tendría un menor y sería (por el teorema de Wagner ) no planar. Klaus Wagner demostró en 1937 que el caso es realmente equivalente al teorema de los cuatro colores y, por lo tanto, ahora sabemos que es verdadero. Como mostró Wagner, cada grafo que no tiene un menor se puede descomponer mediante sumas de camarillas en partes que son planas o una escalera de Möbius de 8 vértices , y cada una de estas partes puede ser 4-coloreada independientemente una de la otra, por lo que la 4-colorabilidad de un grafo sin -menores se sigue de la 4-colorabilidad de cada una de las partes planas. ${\displaystyle k=5}$ ${\displaystyle K_{5}}$ ${\displaystyle k=5}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{5}}$

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

Para , se conocen algunos resultados parciales: cada grafo 7-cromático 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 aristas incidentes como máximo , ^[5] de lo que se deduce que un algoritmo de coloración codicioso 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 grafo sin menor tiene grado medio y, por lo tanto, se puede colorear con colores. Una serie de mejoras de este límite han llevado a una prueba de colorabilidad para grafos 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 para subdivisiones en lugar de menores: es decir, que cada grafo con número cromático contiene una subdivisión de un grafo completo . La conjetura de Hajós es verdadera 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 estrepitosamente para grafos aleatorios : para cualquier , en el límite a medida que el número de vértices, , tiende a infinito, la probabilidad se aproxima a uno de que un grafo aleatorio de -vértice tenga número cromático , y que su subdivisión de clique más grande tenga vértices. En este contexto, vale la pena señalar que la probabilidad también se acerca a uno de que un grafo 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 grafos 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) se preguntó si la conjetura de Hadwiger podría extenderse a la coloración de listas . Para , ${\displaystyle k\leq 4}$ cada grafo con número cromático de lista tiene un clique menor de -vértice . Sin embargo, el número cromático de lista máximo de grafos planares es 5, no 4, por lo que la extensión falla ya para grafos sin -menor . ^[10] De manera más general, para cada , existen grafos 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 cada grafo con número cromático tiene un grafo completo como un menor impar . Tal estructura puede representarse como una familia de subárboles disjuntos en vértices de , cada uno de los cuales es bicolor, de modo que cada par de subárboles está conectado por una arista monocromática. Aunque los grafos sin menor impar no son necesariamente dispersos , se cumple para ellos un límite superior similar al que se cumple para la conjetura estándar de Hadwiger: un grafo sin menor impar 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 )}}$

Al imponer condiciones adicionales a , puede ser posible probar la existencia de menores mayores que . Un ejemplo es el teorema de snark , que establece que todo grafo cúbico que requiera cuatro colores en cualquier coloración de aristas tiene como menor al grafo de Petersen , conjeturado por WT Tutte y anunciado como probado en 2001 por Robertson, Sanders, Seymour y Thomas. ^[13] ${\displaystyle G}$ ${\displaystyle K_{k}}$

Notas

1. Diestel (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 y 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 en esta expresión invoca la notación O mayúscula . ${\displaystyle O}$
6. Kostochka (1984).
7. Thomason (1984).
8. Delcourt y Postle (2024); Norin, Postle y Song (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 conjetura de Hadwiger sobre listas", Electronic Journal of Combinatorics , 18 (1) P232, arXiv : 1110.2272 , doi :10.37236/719, S2CID  13822279
• Bollobás, B. ; Catlin, PA; Erdős, Paul (1980), "La conjetura de Hadwiger es verdadera 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 grafos 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 (julio de 2024), "Reducción de la conjetura lineal de Hadwiger a la coloración de gráficos pequeños", Journal of the American Mathematical Society , arXiv : 2108.01633 , doi :10.1090/jams/1047
• Diestel, Reinhard (2017), "7.3 La conjetura de Hadwiger", Graph Theory , Graduate Texts in Mathematics, vol. 173 (5.ª ed.), Springer, Berlín, págs. 183–186, ISBN 978-3-662-57560-4, Sr.  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; Reed, Bruce ; Seymour, Paul ; Vetta, Adrian (2006), "Sobre la variante impar-menor 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 la coloración de gráficos sin k _menores impares ", Journal of Combinatorial Theory , Serie B, 99 (4): 728–731, doi : 10.1016/j.jctb.2008.12.001 , MR  2518204
• Kawarabayashi, Ken-ichi ; Toft, Bjarne (2005), "Cualquier grafo 7-cromático 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, Luke; Song, Zi-Xia (2023), "Rompiendo la barrera de la degeneración para colorear gráficos sin menor", Advances in Mathematics , 422 109020, 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 American Mathematical Society , 49 (9): 1084–1086
• Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1993), "Conjetura de Hadwiger para grafos libres de K6" (PDF) , Combinatorica , 13 (3): 279–361, doi :10.1007/BF01202354, MR  1238823, S2CID  9608738
• Thomason, Andrew (1984), "Una función extremal para contracciones de grafos", Mathematical Proceedings of the Cambridge Philosophical Society , 95 (2): 261–265, doi :10.1017/S0305004100061521, MR  0735367, S2CID  124801301
• Thomassen, Carsten (1994), "Todo grafo planar es 5-elegible", Journal of Combinatorial Theory , Serie B, 62 (1): 180–181, doi : 10.1006/jctb.1994.1062 , MR  1290638
• Voigt, Margit (1993), "Coloración de listas de grafos planares", Discrete Mathematics , 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 4 colores de Hajós a grafos 4-conectados", Journal of Combinatorial Theory, Serie B , 96 (4): 482–492, doi : 10.1016/j.jctb.2005.10.001 , MR  2232386