En teoría de grafos , una rama de las matemáticas, la construcción de Hajós es una operación sobre grafos que lleva el nombre de György Hajós (1961) y que puede utilizarse para construir cualquier grafo crítico o cualquier grafo cuyo número cromático sea al menos un umbral dado.
Sean G y H dos grafos no dirigidos , vw una arista de G y xy una arista de H. Luego, la construcción de Hajós forma un nuevo grafo que combina los dos grafos identificando los vértices v y x en un único vértice, eliminando las dos aristas vw y xy y agregando una nueva arista wy .
Por ejemplo, supongamos que G y H son cada uno un grafo completo K 4 con cuatro vértices; debido a la simetría de estos grafos, la elección de qué arista seleccionar de cada uno de ellos no es importante. En este caso, el resultado de aplicar la construcción de Hajós es el huso de Moser , un grafo de distancia unitaria de siete vértices que requiere cuatro colores.
Como otro ejemplo, si G y H son gráficos de ciclo de longitud p y q respectivamente, entonces el resultado de aplicar la construcción de Hajós es en sí mismo un gráfico de ciclo, de longitud p + q − 1 .
Se dice que un grafo G es k - construible (o Hajós- k -construible) cuando se forma de una de las siguientes tres maneras: [1]
Es sencillo verificar que cada grafo k -construible requiere al menos k colores en cualquier coloración de grafo adecuada . De hecho, esto es claro para el grafo completo K k , y el efecto de identificar dos vértices no adyacentes es forzarlos a tener el mismo color entre sí en cualquier coloración, algo que no reduce el número de colores. En la construcción de Hajós en sí, la nueva arista wy fuerza a que al menos uno de los dos vértices w e y tenga un color diferente al vértice combinado para v y x , por lo que cualquier coloración adecuada del grafo combinado conduce a una coloración adecuada de uno de los dos grafos más pequeños a partir de los cuales se formó, lo que nuevamente hace que requiera k colores. [1]
Hajós demostró con más fuerza que un grafo requiere al menos k colores, en cualquier coloración propia , si y solo si contiene un grafo k -construible como subgrafo. De manera equivalente, cada grafo k - crítico (un grafo que requiere k colores pero para el cual cada subgrafo propio requiere menos colores) es k -construible. [2] Alternativamente, cada grafo que requiere k colores puede formarse combinando la construcción de Hajós, la operación de identificar dos vértices no adyacentes y las operaciones de agregar un vértice o arista al grafo dado, comenzando desde el grafo completo K k . [3]
Se puede utilizar una construcción similar para colorear listas en lugar de colorear. [4]
Para k = 3 , cada grafo k -crítico (es decir, cada ciclo impar) puede generarse como un grafo k -construible tal que todos los grafos formados en su construcción también sean k -críticos. Para k = 8 , esto no es cierto: un grafo encontrado por Catlin (1979) como un contraejemplo a la conjetura de Hajós de que los grafos k -cromáticos contienen una subdivisión de K k , también sirve como un contraejemplo a este problema. Posteriormente, se encontraron grafos k -críticos pero no k -construibles únicamente a través de grafos k -críticos para todos los k ≥ 4 . Para k = 4 , un ejemplo de esto es el grafo obtenido a partir del grafo del dodecaedro agregando una nueva arista entre cada par de vértices antipodales [5]
Debido a que la fusión de dos vértices no adyacentes reduce el número de vértices en el gráfico resultante, el número de operaciones necesarias para representar un gráfico dado G utilizando las operaciones definidas por Hajós puede exceder el número de vértices en G. [6]
Más específicamente, Mansfield y Welsh (1982) definen el número de Hajós h ( G ) de un grafo k -cromático G como el número mínimo de pasos necesarios para construir G a partir de K k , donde cada paso forma un nuevo grafo combinando dos grafos previamente formados, fusionando dos vértices no adyacentes de un grafo previamente formado, o añadiendo un vértice o arista a un grafo previamente formado. Demostraron que, para un grafo G de n -vértices con m aristas, h ( G ) ≤ 2 n 2 /3 − m + 1 − 1 . Si cada grafo tiene un número de Hajós polinomial, esto implicaría que es posible probar la no colorabilidad en tiempo polinomial no determinista , y por lo tanto implicaría que NP = co-NP , una conclusión considerada improbable por los teóricos de la complejidad. [7] Sin embargo, no se sabe cómo demostrar límites inferiores no polinomiales en el número de Hajós sin hacer alguna suposición de teoría de la complejidad, y si se pudiera demostrar dicho límite, también implicaría la existencia de límites no polinomiales en ciertos tipos de sistemas de Frege en lógica matemática . [7]
El tamaño mínimo de un árbol de expresión que describe una construcción de Hajós para un grafo G dado puede ser significativamente mayor que el número de Hajós de G , porque una expresión más corta para G puede reutilizar los mismos grafos varias veces, una economía no permitida en un árbol de expresión. Existen grafos tricromáticos para los cuales el árbol de expresión más pequeño tiene un tamaño exponencial. [8]
Koester (1991) utilizó la construcción de Hajós para generar un conjunto infinito de grafos poliédricos 4-críticos , cada uno con más del doble de aristas que de vértices. De manera similar, Liu y Zhang (2006) utilizaron la construcción, comenzando con el grafo de Grötzsch , para generar muchos grafos 4-críticos sin triángulos , que demostraron que eran difíciles de colorear utilizando algoritmos de retroceso tradicionales .
En combinatoria poliédrica , Euler (2003) utilizó la construcción de Hajós para generar facetas del conjunto estable politopo .