Obstructions to Total Rainbow Forests in Edge-Colored Graphs

Resumen Técnico: Obstrucciones a los Bosques Arcoíris Totales en Grafos Coloreados por Aristas

Planteamiento del Problema
El artículo investiga la existencia y el tamaño de los "bosques arcoíris" (subgrafos donde no dos aristas comparten el mismo color) en grafos coloreados por aristas. Específicamente, aborda las condiciones bajo las cuales un grafo contiene un bosque arcoíris total —un bosque que incluye exactamente una arista de cada color presente en el grafo. El problema central es caracterizar las obstrucciones a esta existencia: grafos coloreados por aristas que no contienen un bosque arcoíris total y, más específicamente, las obstrucciones mínimas (aquellas que no contienen una obstrucción más pequeña como subgrafo absoluto).

Metodología
Los autores emplean la Teoría de Materias Prima (Matroids), específicamente el Teorema de Intersección de Materias Prima (Edmonds), para analizar la estructura de los grafos coloreados por aristas. Definen dos materias prima sobre el conjunto de aristas $E$ de un grafo $G=(V, E)$ con $n$ vértices y $t$ colores:

1. Matería Prima de Partición ($M_1$): Un conjunto es independiente si contiene como máximo una arista de cada color. Su función de rango $r_1(A)$ cuenta el número de colores distintos en $A$.
2. Matería Prima de Ciclos ($M_2$): Un conjunto es independiente si no contiene ciclos (es decir, es un bosque). Su función de rango $r_2(A) = n - c(A)$, donde $c(A)$ es el número de componentes conexas en el subgrafo inducido por $A$.

Utilizando el Teorema de Intersección de Materias Prima, se determina el tamaño máximo de un bosque arcoíris minimizando la suma de los rangos sobre todos los subconjuntos de aristas. Los autores generalizan un teorema de Suzuki (originalmente para grafos conexos) a grafos no conexos, estableciendo una condición necesaria y suficiente para la existencia de un bosque arcoíris total.

Contribuciones Clave y Resultados

1. La Desigualdad del Bosque Arcoíris y el Teorema Fundamental:
   El artículo establece que un bosque arcoíris total existe si y solo si la Desigualdad del Bosque Arcoíris se cumple para todos los subconjuntos de aristas $A$:
   $$r_1(A) + r_2(E \setminus A) \ge t$$
   Equivalentemente, para cualquier conjunto absoluto $B$ (una unión de clases de colores), la condición se simplifica como:
   $$r_1(B) \le r_2(B)$$
   Si esta desigualdad se viola para cualquier conjunto absoluto $B$ (es decir, $r_1(B) > r_2(B)$), el grafo es una obstrucción.

2. Caracterización de Obstrucciones Mínimas:
   Una obstrucción mínima se define como un grafo coloreado por aristas $B$ donde $r_1(B) > r_2(B)$, pero para cada subgrafo absoluto propio $B' \subset B$, $r_1(B') \le r_2(B')$. El artículo demuestra que las obstrucciones mínimas deben tener al menos 3 colores y orden al menos 3. También establece que una obstrucción mínima no puede contener una clase de color que forme un corte (un conjunto de corte mínimo).

3. Construcción de Diversas Obstrucciones Mínimas:
   Los autores demuestran que las obstrucciones mínimas no son raras; construyen varias familias infinitas y ejemplos específicos, mostrando que el número de obstrucciones mínimas no isomorfas de orden $n$ crece de forma cuadráticamente exponencial. Las construcciones clave incluyen:

   • Ciclos Arcoíris: Cualquier ciclo arcoíris es una obstrucción mínima.
   • Obstrucciones de Vértice Arcoíris: Grafos que contienen un vértice incidente a aristas de $n-1$ colores distintos (un "vértice arcoíris"), donde el resto del grafo es arbitrario (sujeto a restricciones de conectividad). Esta construcción vincula el número de obstrucciones mínimas con el número de grafos no etiquetados de orden $n-1$.
   • Obstrucciones Equinumerosas: Grafos completos $K_n$ coloreados con $n$ colores tales que las clases de colores son casi iguales en tamaño (difieren por al menos 1 arista).
   • Obstrucciones de Vértice Bicolores: Grafos con un vértice incidente a todas las aristas de dos colores específicos, con las aristas restantes distribuidas casi equinumerosamente entre otros colores.
   • Obstrucciones de Bipartición: Coloraciones específicas de $K_n$ que involucran un clique monocromático grande y un $K_2$ complementario.
   • Obstrucciones Desconectadas: Obstrucciones mínimas formadas por la unión disjunta de dos obstrucciones mínimas que comparten un solo color, o mediante la identificación de vértices/aristas entre ellas.
   • Suma de Aristas Coloreadas: Un método para combinar dos obstrucciones mínimas que comparten un color para generar nuevas obstrucciones que no son subgrafos de las originales.

4. Completitud para Órdenes Pequeños:
   El artículo proporciona una clasificación completa de las obstrucciones mínimas para orden $n=3$ (solo el $C_3$ arcoíris) y $n=4$ (el $C_4$ arcoíris, seis coloraciones específicas de $K_4$ y tres coloraciones del grafo diamante $K_4 \setminus e$).

Significancia y Reivindicaciones
El artículo afirma que su principal contribución es la demostración de la existencia de un gran número de diversas obstrucciones mínimas para cualquier orden $n$ (salvo para $n$ trivialmente pequeños). Al utilizar el Teorema de Intersección de Materias Prima, los autores proporcionan un marco riguroso para definir las obstrucciones mediante la violación de la desigualdad de rango $r_1(B) \le r_2(B)$.

Los autores señalan que, si bien encontrar todas las obstrucciones mínimas es probablemente imposible debido al enorme volumen y complejidad de las construcciones (particularmente la familia de vértices arcoíris), su trabajo proporciona una forma sistemática de generarlas. El artículo no pretende resolver el problema de la clasificación general, sino iluminar la estructura de los "subgrafos prohibidos" que impiden la existencia de bosques arcoíris totales. El trabajo fue motivado por posibles aplicaciones al problema del mayor 1-sistema de curvas en una superficie de género $g$, aunque el artículo se centra estrictamente en las obstrucciones de la teoría de grafos.