Conjetura de Hadwiger (teoría de grafos)

La conjetura de Hadwiger (teoría de grafos) es una de las hipótesis no resueltas de la teoría de grafos . Se formula de la siguiente manera: todo grafo -cromático es contráctil a un grafo completo de vértices. $k$ $k$

Otra redacción

La conjetura de Hadwiger se puede formular de manera diferente: en cada gráfico -cromático existen necesariamente subgrafos conectados que no se cruzan, de modo que hay un borde entre dos de ellos. $k$ $k$

Si introducimos para el grafo el número de Hadwiger — el máximo tal que contraemos el grafo completo en los vértices, entonces la hipótesis se formula como la desigualdad , donde es el número cromático del grafo. $h(G)$ $k$ $GRAMO$ $k$ $\chi(G) \leqslant h(G)$ $\ chi (G)$

Casos especiales

Los casos y son obvios: en el primer caso, el grafo contiene al menos una arista, que es el grafo completo ; en el segundo caso, el grafo no es bipartito y contiene un ciclo contraible a . $k=2$ $k = 3$ $K_{2}$ $K_{3}$

La prueba del caso fue publicada por el propio Hadwiger en el mismo periódico en el que se planteó la conjetura. $k = 4$

De la conjetura de Hadwiger en el caso se sigue la validez del problema de los cuatro colores (ahora probado): la operación de contracción conserva la planaridad , y si hubiera un grafo 5-cromático plano, entonces habría una incrustación del grafo en el plano , cuya inexistencia se deriva de la fórmula de Euler . En 1937, Klaus Wagner demostró la equivalencia del problema de los cuatro colores y la conjetura de Hadwiger para , por lo que este caso también está probado. $k = 5$ $K_{5}$ $k = 5$

En 1993, N. Robertson, P. Seymour y Robin Thomas demostraron la conjetura del problema de los cuatro colores. [1] Esta prueba ganó el Premio Fulkerson de 1994 . $k = 6$

Porque se sabe que si el gráfico no satisface la hipótesis, entonces es contractible tanto a como a - gráficos bipartitos completos con partes de cardinalidad 4 y 4 y cardinalidad 3 y 5, respectivamente. $k = 7$ $K_{4,4}$ $K_{3,5}$

Número de Hadwiger

Es posible definir un mapeo que asigne un gráfico máximo tal que contratemos el gráfico completo en los vértices. Encontrar el número de Hadwiger de un gráfico dado es un problema NP-difícil . En cualquier gráfico para el que exista un vértice de grado . [2] Aplicando un algoritmo de coloración de grafos codiciosos , se puede deducir de esta afirmación que . $h(G)$ $GRAMO$ $k$ $GRAMO$ $k$ $GRAMO$ $h(G) = k$ $O(k \raíz cuadrada{\log k})$ $\chi (G) = O(h(G) \sqrt {\log h(G)})$

Véase también

Conjetura de Hadwiger (geometría combinatoria)

Notas

↑ Robertson, Neil; Seymour, Pablo; Thomas, Robin (1993), "Conjetura de Hadwiger para gráficos sin K6" Archivado el 10 de abril de 2009 en Wayback Machine .
↑ Kostochka, AV (1984), "Límite inferior del número de gráficos de Hadwiger por su grado promedio"