Teorema de Gallai-Hasse-Roy-Vitaver

Dualidad de coloraciones y orientaciones de gráficos

Cuatro orientaciones diferentes de un ciclo de cinco ciclos, que muestran un subgrafo acíclico máximo de cada orientación (aristas sólidas) y una coloración de los vértices según la longitud del camino de entrada más largo en este subgrafo. La orientación con los caminos más cortos, a la izquierda, también proporciona una coloración óptima del grafo.

En teoría de grafos , el teorema de Gallai-Hasse-Roy-Vitaver es una forma de dualidad entre las coloraciones de los vértices de un grafo no dirigido dado y las orientaciones de sus aristas. Afirma que el número mínimo de colores necesarios para colorear correctamente cualquier grafo es igual a uno más la longitud de un camino más largo en una orientación elegida para minimizar la longitud de este camino . ^[1] Las orientaciones para las que el camino más largo tiene una longitud mínima siempre incluyen al menos una orientación acíclica . ^[2] ${\displaystyle G}$ ${\displaystyle G}$

Este teorema implica que cada orientación de un grafo con número cromático ${\displaystyle k}$ contiene un camino dirigido simple con vértices; ^[3] este camino puede restringirse para comenzar en cualquier vértice que pueda alcanzar todos los demás vértices del grafo orientado. ^{[4] [5]} ${\displaystyle k}$

Ejemplos

Un grafo bipartito puede estar orientado de un lado a otro de la bipartición. El camino más largo en esta orientación tiene longitud uno, con solo dos vértices. Por el contrario, si un grafo está orientado sin ningún camino de tres vértices, entonces cada vértice debe ser una fuente (sin aristas entrantes) o un sumidero (sin aristas salientes) y la partición de los vértices en fuentes y sumideros muestra que es bipartito. ^[6]

En cualquier orientación de un gráfico de ciclo de longitud impar, no es posible que las aristas alternen su orientación en todo el ciclo, por lo que dos aristas consecutivas deben formar un camino con tres vértices. En consecuencia, el número cromático de un ciclo impar es tres.

Prueba

Para demostrar que el número cromático es mayor o igual que el número mínimo de vértices en un camino más largo, supongamos que un grafo dado tiene una coloración con colores, para algún número . Entonces puede orientarse acíclicamente numerando los colores y dirigiendo cada arista desde su punto final de número más bajo hasta el punto final de número más alto. Con esta orientación, los números aumentan estrictamente a lo largo de cada camino dirigido, por lo que cada camino puede incluir como máximo un vértice de cada color, para un total de como máximo vértices por camino. ^[3] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Para demostrar que el número cromático es menor o igual que el número mínimo de vértices en un camino más largo, supongamos que un grafo dado tiene una orientación con como máximo vértices por camino dirigido simple, para algún número . Entonces los vértices del grafo pueden colorearse con colores eligiendo un subgrafo acíclico máximo de la orientación, y luego coloreando cada vértice por la longitud del camino más largo en el subgrafo elegido que termina en ese vértice. Cada arista dentro del subgrafo está orientada desde un vértice con un número menor a un vértice con un número mayor, y por lo tanto está coloreada correctamente. Para cada arista que no está en el subgrafo, debe existir un camino dirigido dentro del subgrafo que conecte los mismos dos vértices en la dirección opuesta, ya que de lo contrario la arista podría haber sido incluida en el subgrafo elegido; por lo tanto, la arista está orientada desde un número mayor a un número menor y nuevamente está coloreada correctamente. ^[1] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

La prueba de este teorema fue utilizada como caso de prueba para una formalización de la inducción matemática por Yuri Matiyasevich . ^[7]

Interpretación de la teoría de categorías

El teorema también tiene una interpretación natural en la categoría de grafos dirigidos y homomorfismos de grafos . Un homomorfismo es una aplicación de los vértices de un grafo a los vértices de otro que siempre asigna aristas a aristas. Por lo tanto, una coloración de un grafo no dirigido puede describirse mediante un homomorfismo de al grafo completo . Si al grafo completo se le da una orientación, se convierte en un torneo , y la orientación puede levantarse hacia atrás a través del homomorfismo para dar una orientación de . En particular, la coloración dada por la longitud del camino entrante más largo corresponde de esta manera a un homomorfismo a un torneo transitivo (un grafo completo orientado acíclicamente), y cada coloración puede describirse mediante un homomorfismo a un torneo transitivo de esta manera. ^[2] ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle K_{k}}$ ${\displaystyle G}$

Considerando homomorfismos en la otra dirección, hacia ${\displaystyle G}$ en lugar de desde , ${\displaystyle G}$ un grafo ${\displaystyle G}$ dirigido tiene como máximo vértices en su camino más largo si y solo si no hay homomorfismo desde el grafo de camino hacia . ^[2] ${\displaystyle k}$ ${\displaystyle P_{k+1}}$ ${\displaystyle G}$

Por tanto, el teorema de Gallai-Hasse-Roy-Vitaver puede enunciarse de forma equivalente de la siguiente manera:

Para cada grafo dirigido , ${\displaystyle G}$ existe un homomorfismo desde el vértice hasta el torneo transitivo si y solo si no hay homomorfismo desde el camino del vértice hasta . ^[2] ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle (k+1)}$ ${\displaystyle G}$

En el caso que sea acíclico, esto también puede verse 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 el conjunto puede ser dividido. ^[8] Esta afirmación puede generalizarse desde caminos a otros grafos dirigidos: para cada poliárbol hay un grafo dirigido dual tal que, para cada grafo dirigido , hay un homomorfismo de a si y solo si no hay un homomorfismo de a . ^[9] ${\displaystyle G}$ ${\displaystyle P}$ ${\displaystyle D}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle D}$ ${\displaystyle P}$ ${\displaystyle G}$

Historial y resultados relacionados

El teorema de Gallai–Hasse–Roy–Vitaver ha sido redescubierto repetidamente. ^[2] Recibe su nombre de publicaciones separadas de Tibor Gallai , ^[10] Maria Hasse , ^[11] B. Roy, ^[12] y LM Vitaver. ^[13] Roy atribuye el enunciado del teorema a una conjetura en un libro de texto de teoría de grafos de 1958 de Claude Berge . ^[12] Es una generalización de un teorema mucho más antiguo de László Rédei de 1934, que cada torneo (un grafo completo orientado) contiene un camino hamiltoniano dirigido . ^{[14] [15]} El teorema de Rédei se deduce inmediatamente del teorema de Gallai–Hasse–Roy–Vitaver aplicado a un grafo completo no dirigido. ^[14]

En lugar de orientar un grafo para minimizar la longitud de su camino más largo, también es natural maximizar la longitud del camino más corto, para una orientación fuerte (una en la que cada par de vértices tiene un camino más corto). Tener una orientación fuerte requiere que el grafo no dirigido dado sea un grafo sin puentes . Para estos grafos, siempre es posible encontrar una orientación fuerte en la que, para algún par de vértices, la longitud del camino más corto sea igual a la longitud del camino más largo en el grafo no dirigido dado. ^{[16] [17]}

Referencias

1. Hsu, Lih-Hsing; Lin, Cheng-Kuan (2009), "Teorema 8.5", Teoría de grafos y redes de interconexión, Boca Raton, Florida: CRC Press, págs. 129-130, ISBN 978-1-4200-4481-2, Sr.  2454502
2. Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "Sección 3.7: Homomorfismos", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, págs. 39–46, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, Sr.  2920058; véase especialmente el Teorema 3.13, pág. 42
3. Chartrand, Gary ; Zhang, Ping (2009), "Teorema 7.17 (El teorema de Gallai–Roy–Vitaver)", Teoría de grafos cromáticos, Matemáticas discretas y sus aplicaciones, Boca Raton, Florida: CRC Press, ISBN 978-1-58488-800-0, Sr.  2450569
4. Li, Hao (2001), "Una generalización del teorema de Gallai-Roy", Graphs and Combinatorics , 17 (4): 681–685, doi :10.1007/PL00007256, MR  1876576, S2CID  37646065
5. Chang, Gerard J.; Tong, Li-Da; Yan, Jing-Ho; Yeh, Hong-Gwa (2002), "Una nota sobre el teorema de Gallai–Roy–Vitaver", Discrete Mathematics , 256 (1–2): 441–444, doi : 10.1016/S0012-365X(02)00386-2 , MR  1927565
6. Guzmán-Pro, Santiago; Hernández-Cruz, César (2022), "Expresiones orientadas de propiedades de grafos", European Journal of Combinatorics , 105 , artículo n.º 103567, arXiv : 2012.12811 , doi :10.1016/j.ejc.2022.103567, MR  4432176, S2CID  229363421
7. Матиясевич, Ю. B. (1974), "Одна схема доказательств в дискретной математике" [Un cierto esquema para demostraciones en matemáticas discretas], Исследования по конструктивной математике и математической логике [ Estudios en construcción matemáticas y lógica matemática. Parte VI. Dedicado a AA Markov con motivo de su 70 cumpleaños ], Zapiski Naučnyh Seminarov Leningradskogo Otdelenija Matematičeskogo Instituta im. VA Steklova Akademii Nauk SSSR (LOMI) (en ruso), vol. 40, págs. 94-100, SEÑOR  0363823
8. Mirsky, Leon (1971), "Un dual del teorema de descomposición de Dilworth", American Mathematical Monthly , 78 (8): 876–877, doi :10.2307/2316481, JSTOR  2316481
9. Nešetřil, Jaroslav ; Tardif, Claude (2008), "Un enfoque dualista para delimitar el número cromático de un gráfico", European Journal of Combinatorics , 29 (1): 254–260, doi : 10.1016/j.ejc.2003.09.024 , MR  2368632
10. Gallai, Tibor (1968), "Sobre circuitos y grafos dirigidos", Teoría de los grafos (Actas del coloquio celebrado en Tihany 1966) , Budapest: Akadémiai Kiadó, págs.
11. Hasse, Maria (1965), "Zur algebraischen Begründung der Graphentheorie. I", Mathematische Nachrichten (en alemán), 28 (5–6): 275–290, doi :10.1002/mana.19650280503, MR  0179105
12. Roy, B. (1967), "Nombre chromatique et plus longs chemins d'un graphe" (PDF) , Rev. Française Informat. Recherche Opérationnelle (en francés), 1 (5): 129–132, doi : 10.1051/m2an/1967010501291 , SEÑOR  0225683
13. Vitaver, L. M. (1962), "Нахождениечимальных раскрасок вершин графа с помощью булевых степеней матрицы смежностей [Determinación de la coloración mínima de los vértices de un gráfico mediante potencias booleanas de matriz de incidencia]", Doklady Akademii Nauk SSSR (en ruso), 147 : 758–759, MR  0145509
14. Havet, Frédéric (2013), "Sección 3.1: Teorema de Gallai-Roy y resultados relacionados", Orientaciones y coloración de gráficos (PDF) , Apuntes de la escuela de verano SGT 2013 en Oléron, Francia, pp. 15-19
15. Rédei, László (1934), "Ein kombinatorischer Satz", Acta Litteraria Szeged , 7 : 39–43
16. Gutin, G. (1994), "Minimización y maximización del diámetro en orientaciones de grafos", Graphs and Combinatorics , 10 (3): 225–230, doi :10.1007/BF02986669, MR  1304376, S2CID  2453716
17. Bondy, JA (2003), "Pruebas breves de teoremas clásicos", Journal of Graph Theory , 44 (3): 159–165, doi :10.1002/jgt.10135, MR  2012799, S2CID  2174153