Conjuntos independientes y absorbentes por trayectorias monocromáticas

Llamaremos a una digráfica D una digráfica m-coloreada si todas sus flechas están coloreadas con m colores. Una trayectoria dirigida (o un ciclo dirigido) es llamada monocromática si todas sus flechas están coloreadas del mismo color.

Sea D una digráfica m−coloreada, un conjunto N de vértices de D es llamado un núcleo por trayectorias monocromáticas de D si para cada par de diferentes vértices en N no existe trayectoria monocromática entre ellos y para cada vértice v que no pertenece a N existe una trayectoria monocromática de v a algún vértice en N. Un γ-ciclo en D es una sucesión de vértices distintos de D, γ = (u_0,u_1,...,u_{n− 1},u_n = u_0) tal que para cada i ∈ {0,1,...,n − 1}: (i) Existe una u_iu_{i+1}−trayectoria monocromática en D y (ii) No existe ninguna u_{i+1}u_i−trayectoria monocromática en D. Obsérvese que los  índices de los vértices están tomados mod n.

Probaremos algunas condiciones suficientes para la existencia de núcleos por trayectorias monocromáticas en digráficas m−coloreadas que satisfacen que existen dos subdigráficas generadoras D1 y D2 de la digráfica D tales que: F(D1)∩F(D2) = ∅, F (D1) ∪ F (D2) = F (D), colores(D1)∩ colores(D2) = ∅ y cada Di no contienen γ-ciclos para i ∈ {1,2}. Este Teorema puede ser aplicado a todas aquellas digráficas que no contienen γ-ciclos. Generalizaciones de varios resultados previos son obtenidos como una consecuencia directa de este Teorema.