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 las aristas de G. De manera equivalente, el número de Hadwiger h ( G ) es el número más grande n para el cual el grafo completo K n 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 camarilla 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 es siempre al menos tan grande como el número cromático de G .
Los grafos que tienen un número de Hadwiger de cuatro como máximo han sido caracterizados por Wagner (1937). Los grafos con cualquier límite finito en 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 manejable con parámetros fijos .
Un grafo G tiene número de Hadwiger como máximo dos si y sólo si es un bosque , pues un menor completo de tres vértices sólo se puede formar contrayendo un ciclo en G.
Un grafo tiene un número de Hadwiger de como máximo tres si y solo si su ancho de árbol es como máximo dos, lo cual es verdadero si y solo si cada uno de sus componentes biconectados es un grafo serie-paralelo .
El teorema de Wagner , que caracteriza a los grafos planares por sus menores prohibidos , implica que los grafos planares tienen como máximo cuatro números de Hadwiger. En el mismo artículo que demostró este teorema, Wagner (1937) también caracterizó con mayor precisión los grafos con como máximo cuatro números de Hadwiger: son grafos que se pueden formar mediante operaciones de suma de clique que combinan grafos planares con el grafo de Wagner de ocho vértices .
Los gráficos con número de Hadwiger como máximo cinco incluyen los gráficos de vértice y los gráficos incrustables sin enlaces , ambos de los cuales tienen el gráfico completo K 6 entre sus menores prohibidos. [3]
Todo grafo con n vértices y número de Hadwiger k tiene aristas. Esta acotación es estricta: para cada k , existen grafos con número de Hadwiger k que tienen 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 sigue que G debe tener degeneración . Por lo tanto, los grafos con número de Hadwiger acotado son grafos dispersos .
La conjetura de Hadwiger establece que el número de Hadwiger es siempre al menos tan grande como el número cromático de G . Es decir, cada grafo con número de Hadwiger k debería tener una coloración de grafo con como máximo k colores. El caso k = 4 es equivalente (por la caracterización de Wagner de los grafos con este número de Hadwiger) al teorema de los cuatro colores sobre coloraciones de grafos planares , y la conjetura también ha sido probada para k ≤ 5 , pero sigue sin probarse para valores mayores de k . [5]
Debido a su baja degeneración, los gráficos con un número de Hadwiger de como máximo k se pueden colorear mediante un algoritmo de coloración codicioso usando colores.
Probar si el número de Hadwiger de un grafo dado es al menos un valor dado k es NP-completo , [6] de lo que se sigue que determinar el número de Hadwiger es NP-difícil . Sin embargo, el problema es manejable con parámetros fijos : hay un algoritmo para encontrar el menor de clique más grande en una cantidad de tiempo que depende solo polinomialmente del tamaño del grafo, pero exponencialmente en h ( G ) . [7] Además, los algoritmos de tiempo polinomial pueden aproximar el número de Hadwiger significativamente más exactamente que la mejor aproximación de tiempo polinomial (asumiendo 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 al contraer una familia de conjuntos independientes en G.
Los menores de camarilla incontables 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 incontable, 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 )) camarillas (subgrafos completos). [9]
Halin (1976) define una clase de parámetros de grafos que él llama S -funciones, que incluyen el número de Hadwiger. Se requiere que estas funciones, desde grafos hasta números enteros, sean cero en grafos sin aristas , que sean monótonas menores , [a] que aumenten en uno cuando se agrega un nuevo vértice que es adyacente a todos los vértices anteriores, y que tomen el valor más grande de los dos subgrafos a cada lado de un separador de camarilla . El conjunto de todas estas funciones forma una red completa bajo las operaciones de minimización y maximización elemento por elemento. El elemento inferior en esta red es el número de Hadwiger, y el elemento superior es el ancho del árbol .
