En la 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 al contraer los bordes de G. De manera equivalente, el número de Hadwiger h ( G ) es el número k más grande para el cual el gráfico completo K k es un menor de G , el gráfico más pequeño obtenido de G contrayendo aristas y eliminando vértices y aristas. El número de Hadwiger también se conoce como el número de contracción de la camarilla del gráfico G [1] oel grado de homomorfismo del grafo G [2] . El número lleva el nombre de Hugo Hadwiger , quien introdujo el número en 1943 y conjeturó que el número de Hadwiger es siempre al menos el número cromático del gráfico G.
Wagner [3] describe los gráficos con un número de Hadwiger de 4 o menos . Los gráficos con cualquier número de Hadwiger finito son escasos y tienen un número cromático pequeño. Determinar el número de Hadwiger para un gráfico es NP-difícil , pero el problema se puede resolver con parámetros fijos.
Un grafo G tiene un número de Hadwiger como máximo 2 si y solo si es un bosque y se puede formar un menor completo de tres vértices contrayendo un ciclo en G .
Un gráfico tiene un número de Hadwiger de tres o menos si y solo si su ancho de árbol no excede de dos, lo cual se cumple si y solo si alguna de sus bisagras es un gráfico paralelo en serie .
Del teorema de Wagner , que describe los gráficos planos por sus subgráficos prohibidos , se deduce que los gráficos planos tienen un número de Hadwiger que no excede 4. En algunos artículos que contienen la prueba del teorema, Wagner [3] describe gráficos con un número de Hadwiger de cuatro o menos . más precisamente, estos son gráficos, que se pueden formar utilizando operaciones de suma por clic de gráficos planos con un gráfico de Wagner que tiene 8 vértices.
Los gráficos con un número de Hadwiger menor que cinco incluyen gráficos de vértice y gráficos empotrables sin enlaces , ambas familias tienen un gráfico completo K 6 entre los menores prohibidos [4]
Cualquier gráfico con n vértices y número de Hadwiger k tiene aristas O( nk √ log k ). Este límite es exacto: para cualquier k , existe un gráfico con el número de Hadwiger k que tiene aristas Ω( nk √ log k ) [5] [6] [7] . Si un grafo G tiene un número de Hadwiger k , entonces todos sus subgrafos también tienen un número de Hadwiger como máximo k , y esto implica que el grafo G debe tener una degeneración O( k √ log k ). Por lo tanto, los gráficos con un número de Hadwiger acotado son gráficos dispersos .
La conjetura de Hadwiger establece que el número de Hadwiger siempre es al menos el número cromático del gráfico G. Es decir, cualquier gráfico con un número de Hadwiger k debería tener una coloración con k colores como máximo. El caso k = 4 es equivalente (según la caracterización de Wagner de los gráficos con este número de Hadwiger) al problema de los cuatro colores de colorear gráficos planos . La hipótesis también se ha probado para k ≤ 5, pero sigue sin probarse para valores grandes de k [8]
Debido a la baja densidad, los gráficos con un número de Hadwiger que no exceda k se pueden colorear utilizando el algoritmo de coloración codicioso en colores O ( k √ log k ).
Verificar si el número de Hadwiger de un gráfico dado es mayor que algún valor k es un problema NP-completo [9] , lo que implica que determinar el número de Hadwiger es un problema NP-difícil . Sin embargo, el problema es solucionable paramétricamente. — existe un algoritmo para determinar el clic menor más grande en el tiempo, dependiendo solo polinomialmente del tamaño del gráfico, pero exponencialmente de h ( G ) [10] . Además, los algoritmos de tiempo polinomial pueden aproximar el número de Hadwiger con mucha más precisión que la mejor aproximación de tiempo polinomial (suponiendo que P ≠ NP) del tamaño de los subgrafos completos más grandes [10] .
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 gráficos infinitos se pueden caracterizar en términos de refugios , que formalizan estrategias de evasión para algunos juegos de persecución y evitación : si el número de Hadwiger es incontable, es igual al orden del refugio más grande en el gráfico [11] .
Cualquier gráfico con el número de Hadwiger k tiene como máximo n 2 O( k log log k ) cliques (subgrafos completos) [12] .
Halín [2] definió una clase de parámetros gráficos, a los que llamófunciones S. Entre ellos se encuentra el número de Hadwiger. Se requiere que estas funciones de mapeo de gráficos a números enteros tomen cero en gráficos sin bordes , sean monótonas menores , aumenten en uno al agregar un nuevo vértice adyacente a todos los vértices anteriores, y de dos valores para subgráficos en ambos lados del separador de camarilla la función debe tomar un valor mayor. El conjunto de tales funciones forma una red completapor operaciones de toma de elementos mínimos o máximos. El elemento inferior de dicha red es el número de Hadwiger y el elemento superior es el ancho del árbol .