Coincidencia de arco iris
En la disciplina matemática de la teoría de grafos , una coincidencia de arco iris en un gráfico de color de borde es una coincidencia en la que todos los bordes tienen colores distintos.
Dado un gráfico de color de borde G = ( V , E ), un arco iris que coincide con M en G es un conjunto de bordes no adyacentes por pares, es decir, no hay dos bordes que compartan un vértice común, de modo que todos los bordes del conjunto tienen colores distintos.
Una coincidencia máxima de arco iris es una coincidencia de arco iris que contiene el mayor número posible de aristas.
Las coincidencias de arco iris son de particular interés dada su conexión con transversales de cuadrados latinos .
Denote por K n , n el gráfico bipartito completo en n + n vértices. Toda coloración de n - aristas propia de K n , n corresponde a un cuadrado latino de orden n . Una coincidencia de arco iris corresponde a una transversal latina del cuadrado latino, es decir, una selección de n posiciones, una en cada fila y en cada columna, que contienen entradas distintas.
Esta conexión entre transversales latinas y coincidencias de arco iris en K n , n ha inspirado un interés adicional en el estudio de las coincidencias de arco iris en gráficos sin triángulos . [1]
