Número de Hadwiger

En teoría de grafos , el número de Hadwiger de un grafo no dirigido G es el tamaño del grafo completo más grande que se puede obtener contrayendo aristas de G. De forma equivalente, el número de Hadwiger h ( G ) es el mayor número n para el cual el grafo completo Kn es un menor de _G , un grafo más pequeño obtenido a partir de G mediante contracciones de aristas y eliminaciones de vértices y aristas. El número de Hadwiger también se conoce como el número de clique de contracción de G ^{[ 1 ]} o el grado de homomorfismo de G ^{[ 2 ]} . Recibe su nombre de Hugo Hadwiger , quien lo introdujo en 1943 junto con la conjetura de Hadwiger , que establece que el número de Hadwiger siempre es al menos tan grande como el número cromático de G. 

Los grafos con número de Hadwiger como máximo cuatro han sido caracterizados por Wagner (1937) . Los grafos con cualquier límite finito para el número de Hadwiger son dispersos y tienen un número cromático pequeño. Determinar el número de Hadwiger de un grafo es NP-difícil , pero tratable con parámetros fijos .

Un grafo G tiene un número de Hadwiger como máximo dos si y solo si es un bosque , ya que un menor completo de tres vértices solo puede formarse contrayendo un ciclo en G. 

Un grafo tiene un número de Hadwiger como máximo tres si y solo si su ancho de árbol es como máximo dos, lo cual es cierto si y solo si cada uno de sus componentes biconectados es un grafo serie-paralelo .

El teorema de Wagner , que caracteriza los grafos planares por sus menores prohibidos , implica que los grafos planares tienen un número de Hadwiger como máximo cuatro. En el mismo artículo que demostró este teorema, Wagner (1937) también caracterizó con mayor precisión los grafos con número de Hadwiger como máximo cuatro: son grafos que pueden formarse mediante operaciones de suma de cliques que combinan grafos planares con el grafo de Wagner de ocho vértices .

Los grafos con número de Hadwiger como máximo cinco incluyen los grafos ápice y los grafos incrustables sin enlaces , ambos con el grafo completo K ₆ entre sus menores prohibidos. ^{[ 3 ]}

Todo grafo con n vértices y número de Hadwiger k tiene ⁠${\displaystyle O(nk{\sqrt {\log k}})}$aristas. Esta cota es ajustada: para cada k , existen grafos con número de Hadwiger k que tienen${\displaystyle \Omega (nk{\sqrt {\log k}})}$aristas. [ ^{4 ] Si} un grafo G tiene número de Hadwiger k , entonces todos sus subgrafos también tienen número de Hadwiger como máximo k , y se deduce que G debe tener degeneración .${\displaystyle O(k{\sqrt {\log k}})}$⁠ . Por lo tanto, los grafos con número de Hadwiger acotado son grafos dispersos .

La conjetura de Hadwiger afirma que el número de Hadwiger siempre es al menos tan grande como el número cromático de G. Es decir, todo grafo con número de Hadwiger k debería tener una coloración con como máximo k colores. El caso k = 4 es equivalente (según la caracterización de Wagner de los grafos con este número de Hadwiger) al teorema de los cuatro colores en coloraciones de grafos planares , y la conjetura también se ha demostrado para k ≤ 5 , pero sigue sin demostrarse para valores mayores de k . ^{[ 5 ]}  

Debido a su baja degeneración, los grafos con número de Hadwiger como máximo k pueden ser coloreados por un algoritmo de coloración voraz utilizando ⁠${\displaystyle O(k{\sqrt {\log k}})}$colores .

Probar si el número de Hadwiger de un grafo dado es al menos un valor k dado es NP-completo , ^{[ 6 ]} de lo cual se deduce que determinar el número de Hadwiger es NP-difícil . Sin embargo, el problema es tratable con parámetros fijos : existe un algoritmo para encontrar el menor de clique más grande en un tiempo que depende solo polinómicamente del tamaño del grafo, pero exponencialmente de h ( G ) . ^{[ 7 ]} Además, los algoritmos de tiempo polinomial pueden aproximar el número de Hadwiger con una razón de aproximación de${\displaystyle O({\sqrt {n}})}$, significativamente más preciso que la mejor aproximación en tiempo polinomial (suponiendo P  ≠  NP ) al tamaño del subgrafo completo más grande . ^{[ 7 ]}

El número acromático de un grafo G es el tamaño de la camarilla más grande que se puede formar contrayendo una familia de conjuntos independientes en G.

Los menores de clique no numerables en grafos infinitos pueden caracterizarse en términos de refugios , que formalizan las estrategias de evasión para ciertos juegos de persecución-evasión : si el número de Hadwiger es no numerable, entonces es igual al orden más grande de un refugio en el grafo. ^{[ 8 ]}

Todo grafo con número de Hadwiger k tiene como máximo n 2 ^{O ( k log(log k ))} cliques (subgrafos completos). ^{[ 9 ]}

Halin (1976) define una clase de parámetros de grafos que denomina funciones S , entre las que se incluye el número de Hadwiger. Estas funciones de grafos a enteros deben ser cero en grafos sin aristas , ser monótonas respecto a menores , ^{[ a ]} aumentar en uno cuando se añade un nuevo vértice adyacente a todos los vértices anteriores y tomar el mayor valor de los dos subgrafos a cada lado de un separador de clique . El conjunto de todas estas funciones forma un retículo completo bajo las operaciones de minimización y maximización elemento a elemento. El elemento inferior de este retículo es el número de Hadwiger y el elemento superior es el ancho del árbol .