Colorear arcoiris

Ruta en un gráfico de borde coloreado sobre el cual no se repite ningún color

Coloración del arcoíris de un gráfico de rueda , con tres colores. Cada dos vértices no adyacentes se pueden conectar mediante un camino de arcoíris, ya sea directamente a través del vértice central (abajo a la izquierda) o desviándose de un triángulo para evitar un color de borde repetido (abajo a la derecha).

En teoría de grafos , se dice que un camino en un grafo con aristas coloreadas es arcoíris si no se repite ningún color en él. Se dice que un grafo está conexo por arcoíris (o con colores de arcoíris ) si hay un camino arcoíris entre cada par de sus vértices . Si hay un camino más corto arcoíris entre cada par de vértices, se dice que el grafo está fuertemente conexo por arcoíris (o fuertemente coloreado por arcoíris ). ^[1]

Definiciones y límites

El número de conexión del arco iris de un grafo es el número mínimo de colores necesarios para realizar una conexión del arco iris y se denota por . De manera similar, el número de conexión del arco iris fuerte de un grafo es el número mínimo de colores necesarios para realizar una conexión del arco iris fuerte y se denota por . Claramente, cada coloración del arco iris fuerte es también una coloración del arco iris, mientras que lo inverso no es cierto en general. ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle {\text{rc}}(G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle {\text{src}}(G)}$

Es fácil observar que para conectar arcoíris cualquier grafo conexo , necesitamos al menos colors, donde es el diámetro de (es decir, la longitud del camino más largo y más corto). Por otro lado, nunca podemos usar más de colors, donde denota el número de aristas en . Finalmente, debido a que cada grafo fuertemente conexo arcoíris está conexo arcoíris, tenemos que . ${\displaystyle G}$ ${\displaystyle {\text{diam}}(G)}$ ${\displaystyle {\text{diam}}(G)}$ ${\displaystyle G}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle G}$ ${\displaystyle {\text{diam}}(G)\leq {\text{rc}}(G)\leq {\text{src}}(G)\leq m}$

Los siguientes son los casos extremos: ^[1]

• ${\displaystyle {\text{rc}}(G)={\text{src}}(G)=1}$si y solo si es un gráfico completo . ${\displaystyle G}$
• ${\displaystyle {\text{rc}}(G)={\text{src}}(G)=m}$si y solo si es un arbol . ${\displaystyle G}$

Lo anterior muestra que en términos del número de vértices, el límite superior es el mejor posible en general. De hecho, se puede construir una coloración de arco iris usando colores coloreando los bordes de un árbol de expansión de en colores distintos. Los bordes restantes sin colorear se colorean arbitrariamente, sin introducir nuevos colores. Cuando es 2-conexo, tenemos que . ^[2] Además, esto es estricto como lo atestiguan, por ejemplo, los ciclos impares. ${\displaystyle {\text{rc}}(G)\leq n-1}$ ${\displaystyle n-1}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle {\text{rc}}(G)\leq \lceil n/2\rceil }$

Números exactos de conexión de arcoíris o arcoíris fuerte

Se ha determinado el número de conexión del arco iris o del arco iris fuerte para algunas clases de gráficos estructurados:

• ${\displaystyle {\text{rc}}(C_{n})={\text{src}}(C_{n})=\lceil n/2\rceil }$, para cada entero , donde es el gráfico del ciclo . ^[1] ${\displaystyle n\geq 4}$ ${\displaystyle C_{n}}$
• ${\displaystyle {\text{rc}}(W_{n})=3}$, para cada entero , y , para , donde es el gráfico de la rueda . ^[1] ${\displaystyle n\geq 7}$ ${\displaystyle {\text{src}}(W_{n})=\lceil n/3\rceil }$ ${\displaystyle n\geq 3}$ ${\displaystyle W_{n}}$

Complejidad

El problema de decidir si para un gráfico dado es NP-completo . ^[3] Porque si y sólo si , ^[1] se sigue que decidir si es NP-completo para un gráfico dado . ${\displaystyle {\text{rc}}(G)=2}$ ${\displaystyle G}$ ${\displaystyle {\text{rc}}(G)=2}$ ${\displaystyle {\text{src}}(G)=2}$ ${\displaystyle {\text{src}}(G)=2}$ ${\displaystyle G}$

Variantes y generalizaciones

Chartrand, Okamoto y Zhang ^[4] generalizaron el número de conexión del arco iris de la siguiente manera. Sea un grafo conexo no trivial con aristas coloreadas de orden . Un árbol es un árbol arco iris si no se asigna el mismo color a dos aristas de . Sea un entero fijo con . Una coloración de aristas de se denomina coloración -arco iris si para cada conjunto de vértices de , hay un árbol arco iris en que contiene los vértices de . El índice -arco iris de es el número mínimo de colores necesarios en una coloración -arco iris de . Una coloración -arco iris que utiliza colores se denomina coloración -arco iris mínima . Por lo tanto, es el número de conexión del arco iris de . ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle k}$ ${\displaystyle 2\leq k\leq n}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle k}$ ${\displaystyle {\text{rx}}_{k}(G)}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle {\text{rx}}_{k}(G)}$ ${\displaystyle k}$ ${\displaystyle {\text{rx}}_{2}(G)}$ ${\displaystyle G}$

La conexión arcoíris también se ha estudiado en grafos con vértices coloreados. Este concepto fue introducido por Krivelevich y Yuster. ^[5] Aquí, el número de conexión arcoíris de vértices de un grafo , denotado por , es el número mínimo de colores necesarios para colorear de manera tal que para cada par de vértices, haya un camino que los conecte cuyos vértices internos tengan asignados colores distintos. ${\displaystyle G}$ ${\displaystyle {\text{rvc}}(G)}$ ${\displaystyle G}$

Véase también

• Arcoiris a juego

Notas

1. Chartrand et al. (2008).
2. Ekstein y otros (2013).
3. Chakraborty y otros (2011).
4. Chartrand, Okamoto y Zhang (2010).
5. Krivelevich y Yuster (2010).

Referencias

• Chartrand, Gary ; Johns, Garry L.; McKeon, Kathleen A.; Zhang, Ping (2008), "Conexión arcoíris en gráficos", Mathematica Bohemica , 133 (1): 85–98, doi : 10.21136/MB.2008.133947.
• Chartrand, Gary ; Okamoto, Futaba; Zhang, Ping (2010), "Árboles arco iris en gráficos y conectividad generalizada", Networks , 55 (4): NA, doi : 10.1002/net.20339, S2CID  7505197.
• Chakraborty, Sourav; Fischer, Eldar; Matsliah, Arie; Yuster, Raphael (2011), "Dureza y algoritmos para la conexión arcoíris", Journal of Combinatorial Optimization , 21 (3): 330–347, arXiv : 0809.2493 , doi :10.1007/s10878-009-9250-9, S2CID  10874392.
• Krivelevich, Michael ; Yuster, Raphael (2010), "La conexión arcoíris de un gráfico es (como máximo) recíproca a su grado mínimo", Journal of Graph Theory , 63 (3): 185–191, doi :10.1002/jgt.20418.
• Li, Xueliang; Shi, Yongtang; Sun, Yuefang (2013), "Conexiones arco iris de gráficos: una encuesta", Graphs and Combinatorics , 29 (1): 1–38, arXiv : 1101.5747 , doi :10.1007/s00373-012-1243-2, S2CID  253898232.
• Li, Xueliang; Sun, Yuefang (2012), Conexiones de arco iris de gráficos , Springer, pág. 103, ISBN 978-1-4614-3119-0.
• Ekstein, enero; Holub, Premysl; Káiser, Tomaš; Koch, María; Camacho, Esteban Matos; Ryjáček, Zdeněk; Schiermeyer, Ingo (2013), "El número de conexión del arco iris de gráficos de 2 conectados", Matemáticas discretas , 313 (19): 1884–1892, arXiv : 1110.5736 , doi :10.1016/j.disc.2012.04.022, S2CID  16596310.