El teorema de Gallai-Hasse-Roy-Vitaver es una especie de dualidad entre los colores de los vértices de un gráfico no dirigido dado y las orientaciones de sus bordes. El teorema establece que el número mínimo de colores necesarios para una correcta coloración de cualquier gráfico G es uno más que la longitud del camino máximo en la orientación del gráfico G , en el que esta longitud de camino es mínima [1] . Las orientaciones en las que el camino de longitud máxima tiene longitud mínima siempre contienen al menos una orientación acíclica [2] .
Una formulación alternativa del mismo teorema establece que cualquier orientación de un gráfico con número cromático k contiene un camino dirigido simple con k vértices [3] . Es posible imponer condiciones para que el camino comience en cualquier vértice, y que desde ese vértice sea posible llegar a cualquier otro vértice del grafo dirigido [4] [5] .
Un gráfico bipartito se puede orientar de una parte a otra. El camino más largo en esta orientación tiene solo dos vértices. Por el contrario, si una orientación en un gráfico no contiene una ruta de longitud tres, entonces cualquier vértice debe ser una fuente (sin arcos entrantes) o un sumidero (sin arcos salientes), y dividir los vértices en fuente y sumideros muestra que esto el gráfico es bipartito.
En cualquier orientación de un gráfico-ciclo de longitud impar, es imposible dar direcciones diferentes a todas las aristas adyacentes, de modo que dos aristas consecutivas formen un camino con tres vértices. En consecuencia, el número cromático de ciclos impares es tres.
Para probar que el número cromático es mayor o igual que la longitud mínima del camino máximo, supongamos que el gráfico está coloreado con k colores para algún k . Luego, el gráfico se puede orientar de forma acíclica numerando los colores, y cada borde se puede dirigir desde el color con el índice más bajo hacia el más alto. En esta orientación, los índices de color aumentan estrictamente a lo largo de cualquier camino orientado, de modo que cada camino contiene como máximo un vértice de cada color, y el número total de vértices en el camino no puede exceder k (el número de colores).
Para demostrar que el número cromático es menor o igual que la longitud mínima de un camino máximo, supongamos que el grafo tiene una orientación en la que hay como máximo k vértices en cualquier camino orientado para algún k . Los vértices del gráfico se pueden colorear en k colores eligiendo un subgráfico de orientación acíclica máxima y luego coloreando cada vértice con un color con un índice igual a la longitud del camino más largo al vértice dado. Con una coloración de este tipo, cada borde del subgráfico se orienta desde un vértice con un índice más bajo hacia un vértice con un índice más alto y, por lo tanto, la coloración será correcta. Para cada arista que no pertenece al subgrafo, debe haber un camino dirigido dentro del subgrafo que conecte estos dos vértices en dirección opuesta, de lo contrario, la arista caería dentro del subgrafo. Por lo tanto, el borde se orienta de un número mayor a uno más pequeño y no viola la corrección de la coloración [6] .
La prueba de este teorema fue utilizada por Yury Vladimirovich Matiyasevich como caso de prueba para el esquema de prueba propuesto en matemáticas discretas [7] .
El teorema tiene una interpretación natural en las categorías de grafos dirigidos y homomorfismos de grafos . El homomorfismo es un mapeo de vértices de un gráfico a vértices de otro gráfico, en el que los vértices adyacentes permanecen adyacentes en la imagen. Entonces, una coloración k de un grafo no dirigido G puede describirse mediante un homomorfismo del grafo G en el grafo completo K k . Dada una orientación en un gráfico completo, se convierte en un torneo , y esta orientación se puede usar para especificar una orientación en el gráfico G. En particular, la coloración dada por el camino más largo corresponde a un homomorfismo en un torneo transitivo (un gráfico completo orientado acíclicamente), y cualquier coloración puede ser descrita por tal homomorfismo en un torneo transitivo.
Si consideramos homomorfismos en la otra dirección, a G , no desde G , un grafo dirigido G es acíclico y tiene como máximo k vértices en el camino más largo si y solo si no hay homomorfismo de camino P k + 1 a G .
Así, el teorema de Gallai-Hasse-Roy-Vitaver es equivalente al teorema de que para cualquier grafo dirigido G existe un homomorfismo en un torneo transitivo con k vértices si y solo si no hay homomorfismo de un camino con ( k + 1) vértices [2] . En el caso de que el grafo G sea acíclico, el enunciado puede considerarse como una forma del teorema de Mirsky de que la cadena más larga en un conjunto parcialmente ordenado es igual al número mínimo de anticadenas en las que se puede dividir el conjunto [8 ] . La declaración se puede generalizar de caminos a otros gráficos dirigidos: para cualquier poliárbol P existe un gráfico dirigido dual D tal que para cualquier gráfico dirigido G existe un homomorfismo de G a D si y solo si no hay isomorfismo de P a G [9] .
El teorema de Gallai-Hasse-Roy-Vitaver ha sido redescubierto repetidamente [2] . El teorema obtuvo su nombre de publicaciones separadas de T. Gallai [10] , M. Hasse [11] , B. Roy [12] y L. M. Vitaver [13] . Roy atribuye la formulación del teorema a Claude Berge , quien lo planteó como una conjetura en un libro sobre teoría de grafos en 1958 [12] .