Una-introduccion-a-la-coloracion-arcoris

Vista previa del material en texto

UNIVERSIDAD NACIONAL AUTÓNOMA 
 DE MÉXICO 
 
 FACULTAD DE CIENCIAS 
 
 
Una introducción a la coloración arcoíris 
 
 
 
 
 
 
 
 
 
 
 
 
T E S I S 
 
 
 QUE PARA OBTENER EL TÍTULO DE: 
 Matemático 
 P R E S E N T A : 
 
Victor Alfonso López Vázquez 
 
 
 
 
 
 
 
 
 
 
DIRECTOR DE TESIS: 
Dra. María del Rocío Sánchez López 
 
 Ciudad Universitaria, Cd. Mx., 2018 
 
 
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
 
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
 
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
 
 
Índice general
Introducción. 3
1. Preliminares. 6
1.1. Definiciones y algunos resultados útiles. . . . . . . . . . . . . . . . . . . . . . . . 7
1.2. Coloración por aristas y la gráfica de Petersen . . . . . . . . . . . . . . . . . . . 16
2. Coloración arcóıris en gráficas 23
2.1. Primeros resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2. La mı́nima coloración arcóıris y la mı́nima fuerte coloración arcóıris . . . . . . . 33
2.3. rc(G) y src(G) para ciclos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4. Coloración arcóıris para ruedas . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.5. Gráficas bipartitas completas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3. Construcción de gráficas conexas arcóıris. 64
3.1. Construcción de gráficas arcóıris . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Conclusiones. 82
Bibliograf́ıa 83
2
Introducción
El concepto de coloración arcóıris surge a partir de la necesidad de transferir información
entre las agencias gubernamentales de los Estados Unidos.
A partir de los atentados terroristas del 11 de septiembre del 2001 se hizo la siguiente obser-
vación: que ante un inesperado y mortal ataque era necesario la creación de una ley que decrete
que las agencias de inteligencia no podŕıan comunicarse con otras dependencias a través de
canales de radio o sistemas de bases de datos. La tecnoloǵıa utilizada separaŕıa los enlaces de
comunicación y prohibiŕıa los enlaces compartidos, lo que significaŕıa que para los oficiales y
agentes la comunicación en la mayoŕıa de los casos no seŕıa de manera directa, es posible que
la información pasara por varias organizaciones y es aśı que en el año 2003 el departamento
de Homeland Security of USA es creado y es el responsable de descubrir las debilidades en la
transferencia de información clasificada.
Esta situación con lleva a que la información necesita ser protegida y a la vez es necesario
tener procedimientos que permitan el acceso entre las partes apropiadas. Debido a ello nos
enfrentamos a un doble problema. Una manera de resolver estos dos problemas es a través de
la conexión arcóıris concepto que es introducido por primera vez por Gary Chartrand en el año
2006. Dirigiendo la transferencia de información a través de rutas entre agencias que puedan
tener otras agencias intermediarias, esto requerirá una cantidad suficiente de contraseñas o fi-
rewalls para evitar intrusos. Es necesario pensar que entre las rutas de información para dos
agencias distintas estas no repitan password o firewall, ya que aśı seŕıa vulnerable la seguridad
de la red de información. Por lo tanto, esto nos lleva a considerar la siguiente pregunta ¿cuál es
el mı́nimo número de passwords o firewalls distintos que garanticen la seguridad de nuestra red?.
Es aqúı donde esta situación se puede modelar por medio de una gráfica G conexa (donde la
conexidad nos representa que todas las agencias están comunicadas), las agencias las podemos
representar con vértices de G y las aristas son aquellas en las que las agencias tienen una comu-
nicación directa entre ellas. Los passwords los pensaremos como colores. Ahora si consideremos
una función que asigne a las aristas un password, en este caso un color, seŕıa C una coloración
tal que C : A(G) → {1, 2 . . . , n}, con n ∈ N, donde aristas adyacentes pueden ser coloreadas
con el mismo color.
Un camino es arcóıris si dada la coloración C las aristas del camino no repiten color. Ha-
ciendo este planteamiento podremos responder a la interrogante que nos hab́ıamos planteado
anteriormente, y no sólo podremos dar una solución si no que también daremos varias soluciones
para las diversas situaciones que llegarán a presentarse. El tema de coloración arcóıris es una
herramienta para la protección de la información digital.
En el primer caṕıtulo mostramos las definiciones básicas de la teoŕıa de gráficas, conceptos
que son de utilidad para introducir el tema de coloración arcóıris, también exhibimos la gráfica
de Petersen a la cual se le asigna una coloración por aristas, ejemplo en el que nos apoyamos
3
4 INTRODUCCIÓN
para el primer resultado de la tesis.
En el segundo caṕıtulo se ven los primeros resultados en el tema de la coloración arcóıris,
a partir de ello hablamos del entero de la mı́nima coloración arcóıris y el entero de la mı́nima
fuerte coloración arcóıris, mostramos un ejemplo que nos permitan ver como se relacionan estos
dos tipos de coloraciones.
Para cierto tipo de gráficas como son las gráficas completas, gráficas bipartitas completas,
ciclos y gráficas conocidas como ruedas mostraremos cotas inferiores y superiores que nos per-
mitan determinar el entero de la mı́nima coloración y fuerte coloración arcóıris.
En el tercer caṕıtulo vemos que dados dos números enteros que cumplan ciertas propiedades
es posible encontrar una gráfica en donde los valores de la mı́nima y fuerte coloración sean los
enteros dados.
“Es un arcóıris como el resumen, o mejor dicho, principio y fin de todo lo visible”.
Marianela de Benito Pérez Galdós.
Caṕıtulo 1
Preliminares.
En este caṕıtulo mostramos algunos conceptos y resultados básicos que serán de utilidad en
adelante. Se ven las definiciones de algunas gráficas como las gráficas regulares, completas, las
bipartitas completas, subgráfica, subgráfica generadora y ciclos.
Mostramos las definiciones de camino, paseo, trayectoria y geodésica. A partir de ello la de-
finición de longitud de una trayectoria, distancia, excentricidad, radio, diámetro y por último la
matriz de adyacencia. Con el concepto de trayectoria entre dos vértices definimos la conexidad
de una gráfica esta definición es fundamental para hablar de la coloración arcóıris.
6
1.1. DEFINICIONES Y ALGUNOS RESULTADOS ÚTILES. 7
1.1. Definiciones y algunos resultados útiles.
Definición 1.1. Una gráfica G es una pareja ordenada de un conjunto de objetos finitos no
vaćıo llamados vértices y otro conjunto de pares no ordenados de vértices distintos llamados
aristas.
El conjunto de vértices de la gráfica G se denota como V (G), mientras que el conjunto de
aristas lo denotamos como A(G). A una arista se le representa como uv donde u y v son sus
vértices extremos.
En adelante consideraremos que para toda gráfica G sólo hay a lo más una arista entre todo
par de vértices.
Definición 1.2. Sean G una gráfica y {u, v} ⊆ V (G). Se dice que u y v son vértices adya-
centes, si uv ∈ A(G).
Definición 1.3. Sean G una gráfica y {a1, a2} ⊆ A(G) tales que a16= a2. Decimos que a1 y a2
son aristas adyacentes si éstas comparten un vértice extremo.
La cardinalidad del conjunto de vértices de G es llamado el orden de G y se denota por n .
Por otro lado, la cardinalidad del conjunto de aristas es el tamaño de la gráfica G y se denota
por m . Decimos que una gráfica G tiene tamaño m y orden n.
Definición 1.4. Una representación geométrica de una gráfica G es una interpretación
geométrica donde a los vértices de G se les identifica con un punto en el plano mientras que
una arista es un segmento de recta delimitado por dos puntos correspondientes a los extremos
de la arista (vértices).
En la figura 1.1 se muestra la representación geométrica de tres gráficas. Donde, para la
gráfica G1 tenemos: V (G1) = {v1, v2, v3} y A(G1) = {v1v2, v2v3, v3v1}. Para la gráfica G2
tenemos: V (G2) = {v1, v2, v3, v4, v5} y A(G2) = {v1v2, v1v3, v1v4, v1v5}. Por último para la
gráfica G3 tenemos: V (G3) = {v1} y A(G3) = ∅.
Figura 1.1: Representación geométrica de las gráficas G1,G2 y G3.
Observemos que:
1. G1 tiene orden n = 3 y tamaño m = 3.
8 CAPÍTULO 1. PRELIMINARES.
2. G2 tiene orden n = 5 y tamaño m = 4.
3. G3 tiene orden n = 1 y tamaño m = 0.
Definición 1.5. El grado de un vértice v en una gráfica G es el número de aristas de G que
tienen como extremo al vértice v, es denotado por δ(v) ó δG(v).
A un vértice se le llamará par o impar si tiene grado par o impar respectivamente. Se
dice que un vértice es aislado si tiene grado 0. A un vértice de grado 1 se le llamará vértice
terminal.
Definición 1.6. Sea G una gráfica. El grado mı́nimo de G se define como el
mı́n{δ(v)|v ∈ V (G)} y se denota por δ(G).
Definición 1.7. Sea G una gráfica. El grado máximo de G se define como el
máx{δ(v)|v ∈ V (G)} y se denota por ∆(G).
Consideremos las gráficas en la figura 1.1 y veamos el grado máximo y mı́nimo:
1. En G1 tenemos que δ(G1) = 2 y ∆(G1) = 2.
2. En G2 tenemos que δ(G2) = 1 y ∆(G2) = 4.
3. En G3 tenemos que δ(G3) = 0 y ∆(G3) = 0.
Definición 1.8. Sea G una gráfica. Decimos que G es regular de grado r con r ∈ N, si
δG(v) = r para cada vértice v de G.
Las gráficas de la definición anterior son llamadas r-regulares.
A una gráfica 3-regular la llamaremos una gráfica cúbica. Por ejemplo, la gráfica de la
figura 1.2 (conocida como la gráfica de Petersen) es una gráfica cúbica.
Figura 1.2: La gráfica de Petersen, con dos de sus representaciones.
Definición 1.9. Sea G una gráfica. G es completa si para cualquier {u, v} ⊆ V (G), u y v
son adyacentes. A estas gráficas completas de orden n las denotamos por Kn.
Note que una gráfica completa Kn es una gráfica regular de grado n−1 y tamaño m = n(n−1)2 .
1.1. DEFINICIONES Y ALGUNOS RESULTADOS ÚTILES. 9
Definición 1.10. Sean G una gráfica y S ⊆ V (G). S es un conjunto independiente si para
cualquier {u, v} ⊆ S se tiene que uv /∈ A(G).
A continuación definiremos una gráfica k-partita.
Definición 1.11. Sean G una gráfica y k ∈ N tal que k ≥ 2. Decimos que G es k-partita si
existe una partición de los vértices de G en k conjuntos independientes.
A las gráficas 2-partitas decimos que son gráficas bipartitas. A la gráfica k-partita con
partición de sus vértices en k conjuntos independientes donde a cada par de vértices en conjuntos
distintos son adyacentes, se le conoce como una gráfica k-partita completa.
Definición 1.12. Sea G una gráfica. Un camino en G es una sucesión finita de vértices tal
que ui−1ui ∈ A(G) para cada i ∈ {1, 2, . . . , k}, iniciando en el vértice u0 y terminando en el
vértice uk. Decimos que C = (u0, u1, u2 . . . , uk−1, uk) es un u0uk-camino.
La definición anterior nos permite introducir lo siguiente:
Definición 1.13. Sean G una gráfica y C = (u0, . . . , uk) un camino en G. Definimos el camino
inverso de C, como C−1 = (uk, uk−1, . . . , u1, u0) una sucesión finita de vértices tal que
ui−1ui ∈ A(G) para cada i ∈ {1, 2, . . . , k}, iniciando en el vértice uk y terminando en el vértice
u0.
Definición 1.14. Sean G una gráfica y C = (u0, . . . , xi, . . . , xj, . . . , uk) un camino en G. Para
xi y xj, con i < j, el subcamino (xi, xi+1, . . . , xj−1, xj) contenido en C es denotado por
(xi, C, xj).
Definición 1.15. Sean G una gráfica y C = (u0, . . . , uk) un camino, con k ∈ N. Decimos que
la longitud del camino C es k y es denotado por l(C).
Un camino es trivial cuando k = 0, es decir, no tiene aristas, en este trabajo considerare-
mos caminos no triviales. Notemos que en los caminos está permitida la repetición de aristas y
vértices por lo que en una gráfica es común encontrar distintos tipos de caminos. Un uv-camino
que no repite aristas se le conoce como un uv-paseo, mientras que un uv-camino que no repite
vértices se dice que es una uv-trayectoria.
Los caminos tienen una caracteŕıstica: Un uv-camino es cerrado o abierto dependiendo si
u 6= v o si u = v, es decir, si el camino C comienza y termina con el mismo vértice entonces C
es un camino cerrado. Ahora, es abierto cuando el camino C inicia en un vértice y termina en
otro distinto, es decir, u 6= v.
Definición 1.16. Sean G una gráfica y γ un camino cerrado en G. Decimos que γ es un ciclo
si γ no repite vértices con excepción del primer y último vértice y l(γ) ≥ 3.
Definición 1.17. Sean G una gráfica y γ = (u1, u2, u3, . . . , un, u1) un ciclo. Decimos que γ es
un ciclo de longitud n.
De las definiciones anteriores notemos que para algunos resultados es mucho más cómodo
trabajar con trayectorias que con caminos, por lo que es necesario el siguiente teorema.
10 CAPÍTULO 1. PRELIMINARES.
Teorema 1.1. Todo uv−camino contiene una uv-trayectoria.
Demostración. Sean G una gráfica y n ∈ N. Procederemos por inducción sobre la longitud del
camino.
Base de inducción. Sea (u, v) un uv-camino en la gráfica G de longitud 1, entonces es una
uv-trayectoria.
Hipótesis de inducción. Si C
′
es un uv-camino de longitud menor a n entonces C
′
contiene
una uv-trayectoria.
Ahora sea C = (u = x0, x1, x2, . . . , xn = v) un uv-camino de longitud n. Mostraremos que
C contiene una uv-trayectoria.
Consideremos los siguientes casos, respecto a los vértices de C.
Caso 1.- xi 6= xj para toda i 6= j.
En este caso C es una uv-trayectoria.
Caso 2.- xi = xj para i 6= j.
En este caso proponemos C = (u = x0, x1, . . . , xi−1, xi, xi+1, . . . , xj−1, xj = xi, . . . , xn = v).
Consideremos un subcamino de C como C
′
= (x0, x1, . . . , xi−1, xi = xj, xj+1, . . . , xn), notemos
que l(C
′
) < l(C) = n y por hipótesis de inducción C
′
contiene una uv-trayectoria. Como C
′
está contenido en C, entonces C contiene una uv-trayectoria.
El concepto de camino y el resultado anterior nos permite definir lo siguiente:
Definición 1.18. Sean G una gráfica y {u, v} ⊆ V (G). Decimos que G es conexa si para todo
{u, v} ⊆ V (G) existe una uv-trayectoria.
Si existen dos vértices en G para los cuales no existe una trayectoria, entonces G es inconexa.
Antes de ver algunos resultados de conexidad definamos lo siguiente.
Sean G una gráfica y a ∈ A(G) definimos a la gráfica G \ a como la gráfica que tiene por
vértices V (G \ a) = V (G) y por aristas A(G \ a) = A(G) \ {a}.
Un resultado importante de conexidad es el siguiente.
Teorema 1.2. Si G una gráfica conexa no trivial y γ un ciclo de la gráfica G, entonces G \ a
es conexa para toda a ∈ A(γ).
Demostración. Sea a ∈ A(γ) supongamos sin pérdida de generalidad que a = xixi+1. Mostra-
remos que para todo {u, v} ⊆ V (G \ a) existe una uv-trayectoria en G \ a.
Sean u ∈ V (G \ a) y v ∈ V (G \ a), consideremos los siguientes casos.
Caso 1.- u = xi y v = xj.
1.1. DEFINICIONES Y ALGUNOS RESULTADOS ÚTILES. 11
Para este caso la trayectoria T = (xi, γ
−1, xi+1) es una xixj-trayectoria. Por lo tanto, G \ a
es conexa.
Caso 2.- u 6= xi y v 6= xj y {u, v} ⊆ V (γ).
Supongamos sin pérdida de generalidad que u = xα y v = xβ con α < β, para este caso
tenemos que T = (xα, γ, xβ) es una xαxβ-traeyectoriaen G \ a. Por lo tanto, G \ a es conexa.
Caso 3.- {u, v} * V (γ).
Como G es conexa y {u, v} * V (γ) podemos considerar a T1 una uxi-trayectoria y a T2
una vxi+1-trayectoria, sabemos por los casos anteriores que para cualesquiera par de vértice en
el ciclo existe una trayectoria entre ellos por ello proponemos a T3 una xixi+1-trayectoria. Aśı,
C = (u, T1, xi, T3, xi+1, T
−1
2 , v) es un uv-camino y por teorema 1.1 existe una uv-trayectoria en
G \ a. Por lo tanto, G \ a es conexa.
Definición 1.19. Sean G y H dos gráficas. Decimos que H es una subgráfica de G si
V (H) ⊆ V (G), con V (H) 6= ∅, y A(H) ⊆ A(G). Lo denotamos por H ⊆ G.
Mencionamos que H no es subgráfica de G si H * G.
Definición 1.20. Sean G y H dos gráficas. Decimos que H es una subgráfica generadora
de la gráfica G si H es una subgráfica de G y V (H) = V (G).
Definición 1.21. Sean G una gráfica y H una subgráfica de G. Decimos que H es una com-
ponente de G si H es conexa y máxima por contención con la propiedad de ser conexa.
Definición 1.22. Sean G una gráfica y {u, v} ⊆ V (G). La distancia entre u y v es la mı́nima
de las longitudes entre todas las uv-trayectorias de G y se denotada por d(u, v).
Observación 1.1. Sean G una gráfica y {u, v} ⊆ V (G). Si G es inconexa, entonces decimos
que la distancia entre los vértices de una misma componente está definida y si u y v están en
componentes distintas se dice que d(u, v) es indefinida ó d(u, v) =∞.
Notemos que la función de distancia d(u, v) : V (G)×V (G)→ R+ con el conjunto de vértices
V (G) es un espacio métrico, es decir, se tienen las siguientes propiedades cuando G es conexa.
1. Para cualquier subconjunto {u, v} ⊆ V (G) se cumple d(u, v) > 0 y d(u, v) = 0 si y sólo
si u = v.
2. Para cualquier subconjunto {u, v} ⊆ V (G) se cumple d(u, v) = d(v, u) (propiedad simétri-
ca).
3. Para cualquier subconjunto {u, v, w} ⊆ V (G) se cumple d(u,w) ≤ d(u, v) + d(v, w) (de-
sigualdad del triángulo).
A continuación probaremos que d(u, v) : V (G)× V (G)→ R+ es una métrica.
Demostración. 1. Sea u ∈ V (G) y v ∈ V (G) supongamos que u 6= v, como los vértices u y
v son distintos y por la observación 1.1 se cumple que d(u, v) > 0 ya que para cualquier
uv-trayectoria es de longitud mayor a cero.
12 CAPÍTULO 1. PRELIMINARES.
Por otra parte si u = v, sea T (u, v) una uv-trayectoria notemos que l(T ) = 0, entonces T
es una trayectoria de longitud mı́nima. Aśı, d(u, v) = 0.
Ahora si d(u, v) = 0 implica que la trayectoria de longitud mı́nima tiene por longitud
cero esto implica que u = v. Por lo tanto, para todo par {u, v} ⊆ V (G) se tiene que
d(u, v) ≥ 0.
2. Sea T una uv-trayectoria en G, con l(T ) = d(u, v). Como T−1 es una vu-trayectoria y
l(T−1) = l(T ) = d(u, v), entonces d(v, u) ≤ l(T ′) = d(u, v). Por lo tanto, d(v, u) ≤ d(u, v).
Por otro lado, sea T
′
una vu-trayectoria en G con, l(T
′
) = d(v, u). Como (T
′−1) es una
uv-trayectoria y l(T
′−1) = l(T
′
) = d(v, u) entonces d(u, v) ≤ l(T ′−1) = d(v, u). Por lo
tanto, d(u, v) ≤ d(v, u).
Por las desigualdades anteriores tenemos que d(u, v) = d(v, u).
3. Sean G una gráfica, T = (u, . . . , w) una uw-trayectoria tal que l(T ) = d(u,w),
T1 = (u, . . . , v) una uv-trayectoria tal que l(T1) = d(u, v) y T2 = (v, . . . , w) una vw-
trayectoria tal que l(T2) = d(v, w). Ahora proponemos a T1 ∪ T2 = (u, T1, v, T2, w). Como
T1 ∪ T2 es un uw-camino entonces se sigue del teorema 1.1 que T1 ∪ T2 contiene a T
′
una
uw-trayectoria. Aśı, por definición de distancia.
d(u,w) = l(T ) ≤ l(T ′) ≤ l(T1 ∪ T2) = l(T1) + l(T2)
d(u,w) = l(T ) ≤ l(T1) + l(T2) = d(u, v) + d(v, w)
d(u,w) ≤ d(u, v) + d(v, w)
Definición 1.23. Sean G una gráfica y {u, v} ⊆ V (G). Una uv-geodésica en G es una
uv-trayectoria T tal que l(T ) = d(u, v).
Definición 1.24. Sean G una gráfica y {u, v} ⊆ V (G). La excentricidad de un vértice v,
es denotada por e(v) y se define como máx{d(u, v)| u ∈ V (G)}.
Definición 1.25. Sea G una gráfica. El radio de G está definido por mı́n{e(v)| v ∈ V (G)},
lo denotamos por rad(G).
Definición 1.26. Sea G una gráfica. El diámetro de G se define como máx{e(v)|v ∈ V (G)},
lo denotamos por diám(G).
Un resultado importante de ciclos que se relaciona con los conceptos anteriores es el siguiente.
Proposición 1.1. Si γn = (v1, v2, . . . , vn, v1) es un ciclo de longitud n con n ∈ N, entonces
diám(γn) = bn2 c.
Demostración. Sea γn = (v1, v2, . . . , vn, v1), definimos bn2 c = k y k ∈ N. Mostraremos que el
diám(γn) =máx{e(v)| v ∈ V (γn)} = k.
Consideremos los siguientes casos con respecto a longitud del ciclo.
1.1. DEFINICIONES Y ALGUNOS RESULTADOS ÚTILES. 13
Caso 1.- n = 2k.
Fijemos los vértices {vk, v2k} ⊆ V (γn) y como están contenidos en un ciclo para los vérti-
ces vi y vj existe únicamente dos trayetorias además distintas, consideremos las trayectorias
P1 = (v2k, γn, vk) y P2 = (v2k, γ
−1
n , vk) notemos que l(P1) = l(P2) = k y e(v2k) = d(v2k, vk) = k.
Figura 1.3: Un ciclo γ2k.
Consideremos los siguientes subcasos con respecto a los vértices {vi, vj} ⊆ V (γn) con
1 ≤ i < j ≤ 2k.
Subcaso 1.i.- {vi, vj} ⊆ V (P1).
En este caso las únicas vivj-trayectorias en el ciclo son: T1 = (vi, γn, vj) y T2 = (vi, γ
−1
n , v2k)
∪ P2 ∪ (vk, γ−1n , vj), observemos que T2 ⊂ P2, si v2k = vi entonces vj 6= vk y viceversa ya que
de lo contrario seŕıa el caso anterior, entonces l((vi, γ
−1
n , v2k)) ≥ 1 o l((vk, γ−1n , vj)) ≥ 1, por lo
anterior, l(T2) > k por otra parte T1 ⊆ P1 entonces l(T1) < k. Por lo tanto, l(T1) = d(vi, vj) < k.
Para el subcaso en que {vi, vj} ⊆ V (P2) se procede de forma análoga.
Subcaso 1.ii.- vi ∈ V (P1) y vj ∈ V (P2).
Consideremos las trayectorias T3 = (vi, γn, vk)∪(vk, γn, vj) y T4 = (vi, γ−1n , v2k)∪(v2k, γ−1n , vj),
notemos que l(T3) + l(T4) = 2k.
Si suponemos que l(T3) = k, entonces l(T4) = k por lo que para los vértices vi y vj la
d(vi, vj) = l(T4) = k, por otra parte si l(T3) > k, entonces l(T4) < k ya que γn es un ci-
clo de longitud 2k, aśı l(T4) = d(vi, vj) < k, si l(T3) < k, entonces l(T4) > k por lo que
l(T3) = d(vi, vj) < k.Por lo tanto, diám(γn) = bn2 c = k con n = 2k.
Caso 2.- n = 2k + 1.
Fijemos los vértices v2k+1 y vk y consideremos las v2k+1vk-trayectorias P1 = (v2k+1, γn, vk) y
P2 = (v2k+1, γ
−1
n , vk), notemos que l(P1) = k + 1 y l(P2) = k.
14 CAPÍTULO 1. PRELIMINARES.
Figura 1.4: Un ciclo γ2k+1.
Consideremos los siguientes subcasos con respecto a los vértices {vi, vj} ⊆ V (γn) con
1 ≤ i < j ≤ 2k + 1.
Subcaso 2.i.- {vi, vj} ⊆ V (P1).
Para las trayectorias T1 = (vi, γn, vj) y T2 = (vi, γ
−1
n , v2k+1) ∪ (v2k+1, γ−1n , vk) ∪ (vk, γ−1n , vj),
para este caso notemos que si vi = v2k+1, entonces vj 6= vk y viceversa ya que de lo contrario
estariamos en el caso 2.ii, como T1 ⊆ P1 y por la consideración anterior l(T1) ≤ k, aśı l(T2) > k
ya que γn es un ciclo de longitud impar. Por lo tanto, l(T1) = d(vi, vj) ≤ k.
Subcaso 2.ii.- {vi, vj} ⊆ V (P2).
Para las trayectorias T3 = (vi, γ, vj) y T4 = (vi, γ
−1
n , vk)∪P−11 ∪ (v2k+1, γ−1n , vj), notemos que
T3 ⊆ P2, entonces l(T3) ≤ l(P2) = k como γn es un ciclo de longitud 2k+ 1 entonces l(T4) > k.
Aśı, l(T3) = d(vi, vj) ≤ k.
Subcaso 2.iii.- vi ∈ P1 y vj ∈ P2.
Consideremos las trayectorias T5 = (vi, γn, vj) y T6 = (vi, γ
−1
n , vj), como γn es un ciclo de
longitud impar, entonces l(T5) + l(T6) = 2k + 1.
Si l(T5) = k, entonces l(T6) = k+1, por lo que l(T5) = d(vi, vj) = k, si l(T5) ≥ k+1, entonces
l(T6) = d(vi, vj) ≤ k, si l(T5) ≤ k − 1 entonces l(T6) ≥ k + 2, aśı l(T5) = d(vi, vj) < k − 1. Por
lo tanto, el diám(γn) = bn2 c con n = 2k + 1.
Una gráfica está completamente determinada por sus adyacencias o incidencias. Esta infor-
mación se puede expresar de forma conveniente en una matriz. Por lo anterior es necesario dar
la siguiente definición.
Definición 1.27. Sea G una gráfica con conjunto de vértices V (G) = {v1, v2, v3, . . . , vn}, para
alguna n ∈ N. La matriz de adyacencia es una matriz de n×n, denotada por A[G] = [aij],
donde a la entrada aij de la matrizA[G] se define como:
aij =
{
1 si vivj ∈ A(G)
0 si vivj /∈ A(G).
1.1. DEFINICIONES Y ALGUNOS RESULTADOS ÚTILES. 15
Teorema 1.3. Si G es una gráfica, V (G) = {v1, . . . , vn} y A[G] la matriz de adyacencia de G,
entonces la entrada apij de A
p[G] es el número de los distintos caminos de longitud p de vi a vj.
Demostración. Haremos la demostración por inducción sobre p.
Base de inducción. Para p = 1 tenemos que Ap[G] = A1[G] = A[G] donde:
aij =
{
1 si vivj ∈ A(G)
0 si vivj /∈ A(G).
Notemos que una arista induce un camino de longitud 1 y rećıprocamente los caminos de lon-
gitud uno son aristas. Por lo tanto, aij representa los caminos de longitud 1 de vi a vj en G.
Hipótesis de inducción. Supondremos válido para p, es decir, apij de A
p[G] es el número de
caminos de longitud p de vi a vj.
Mostraremos que la entrada ap+1ij de la matriz A
p+1 es el número de caminos de longitud
p+ 1 de vi a vj.
ap+1ij =
n∑
k=1
apikakj con 1 ≤ i ≤ n y 1 ≤ j ≤ n. Observemos que a
p
ik representa todos los
caminos de vi a vk de longitud p y akj representa los caminos entre los vértices vk y vj de
longitud 1 con akj ∈ {0, 1}, entonces
n∑
k=1
apikakj =
∑
vr∈N(vj)
ap+1ij . Por lo tanto, a
p
ikakj representa
los caminos de longitud p+1 entre los vértices vi a vj que pasan por vk con vk en los vecinos de vj.
Por lo tanto, la entrada ap+1ij de A
p+1[G] es el número de los distintos caminos de longitud
p+ 1 de vi a vj.
Corolario 1.1. Sea G una gráfica conexa no trivial y A[G] su matriz de adyacencia. Para
{vi, vj} ⊆ V (G) se tiene que d(vi, vj) es el mı́nimo k tal que la entrada aij de Ak[G] es distinta
de cero.
Demostración. Procederemos por contradicción. Sean {vi, vj} ⊆ V (G) con i < j y d(u, v) = k,
supongamos que existe k
′ ∈ N tal que para la entrada akij de Ak[G] es distinta de cero y
0 < k
′
< k.
Por el teorema 1.3 la entrada ak
′
ij representa las distintos caminos de longitud k
′
entre los
vértices vi y vj, como k
′ 6= 0 existe C un vivj-camino y utilizando el teorema 1.1, tenemos a T
una vivj-trayectoria.
Notemos que l(T ) ≤ l(C) = k′ < k. Aśı, l(T ) < k = d(vivj) contradiciendo al hecho de ser
d(vi, vj) la mı́nima longitud entre todas las vivj-trayectorias. Por lo tanto, d(vi, vj) es el mı́nimo
k tal que la entrada aij de A
k[G] es distinta de cero.
En la figura 1.5 se ejemplifica el concepto de la matriz de adyacencia para una gráfica G1.
16 CAPÍTULO 1. PRELIMINARES.
Figura 1.5: La gráfica G1.
Para la gráfica G1 obtenemos su matriz de adaycencia.
A[G1] =

v1 v2 v3 v4
v1 0 1 0 1
v2 1 0 1 1
v3 0 1 0 1
v4 1 1 1 0

A partir de la matriz de adyacencia obtenemos A2[G1] que muestra todas los caminos de
longitud 2 en la gráfica.
A2[G1] =

v1 v2 v3 v4
v1 2 1 2 1
v2 1 3 1 2
v3 2 1 2 1
v4 1 2 1 3

A partir de la matriz A2[G1] se nota que los caminos de longitud 2 son: (v1, v2, v3), (v1, v4, v3)
que son los caminos entre los vértices v1 y v3 y los caminos (v2, v1, v4), (v2, v3, v4) que son los
caminos entre los vértices v1 y v4. Ver figura 1.5.
1.2. Coloración por aristas y la gráfica de Petersen
En esta sección damos las definiciones de coloración, coloración propia por aristas, k-
coloración propia por aristas, k-coloreable por aristas, ı́ndice cromático de una gráfica y mos-
tramos la gráfica de Petersen. Aportamos una coloración propia por aristas de la gráfica de
Petersen, también determinamos el ı́ndice cromático. Esto es de utilidad para ejemplificar los
conceptos de la coloración arcóıris.
Definición 1.28. Sea G una gráfica con al menos una arista y C : A(G)→ {1, 2, . . . , n} una
función con n ∈ N. Decimos que C es una coloración de las aristas de G.
Definición 1.29. Sea G una gráfica y C : A(G) → {1, 2, . . . , n} una función. Para
{a, f} ⊆ A(G), con a adyacente a f , si C(a) 6= C(f), entonces decimos que C es una colo-
ración propia por aristas de G.
Definición 1.30. Si G una gráfica, C : A(G)→ {1, 2, . . . , k} una coloración propia por aristas
tal que C es una función sobreyectiva. Se dice que C es una k-coloración propia por aristas
de G.
Definición 1.31. Sea G es una gráfica. Decimos que G es k-coloreable por aristas si existe
C una k-coloración propia por aristas de G.
Definición 1.32. Si G una gráfica, el mı́nimo entero positivo k tal que G es k-colorable por
aristas es el ı́ndice cromático de G y se le denota por χ
′
(G).
1.2. COLORACIÓN POR ARISTAS Y LA GRÁFICA DE PETERSEN 17
A continuación damos un ejemplo de una k-coloración propia por aristas.
Figura 1.6: La gráfica de Petersen es 4-coloreable por aristas.
Proposición 1.2. El ı́ndice cromático de la gráfica de Petersen es χ
′
(P ) = 4.
Demostración. Como en la figura 1.6 se exhibe una 4-coloración propia por aristas de la gráfica
de Petersen se tiene que χ
′
(P ) ≤ 4.
Falta demostrar que 4 ≤ χ′(P ) supongamos lo contrario que χ′(P ) ≤ 3. Sea C una 3-coloración
propia por aristas. Notemos que la gráfica de Petersen es 3-regular. Aśı para cada vértice en
P inciden tres aristas y como C es una 3-coloración propia estas aristas deben tener un color
distinto.
Figura 1.7: C(u5u1) = 1, C(u7u1) = 2 y C(u2u1) = 3.
Por lo anterior fijémonos en el vértice u1 y en las aristas u5u1, u7u1 y u2u1; notemos que
estas aristas son adyacentes y como C es una 3-coloración se tienen las siguientes posibilidades
{C(u5u1), C(u7u1), C(u2u1)} ⊆ {1, 2, 3}.
18 CAPÍTULO 1. PRELIMINARES.
Supongamos sin pérdida de generalidad que C(u5u1) = 1, C(u7u1) = 2 y C(u2u1) = 3 (ver
figura 1.7).
Esto implica que para las aristas {C(u5u4), C(u6u5)} ⊆ {2, 3}, {C(u9u7), C(u10u7)} ⊆ {1, 3}
y {C(u8u2), C(u3u2)} ⊆ {1, 2}. Ahora veamos el siguiente caso:
Caso 1.- C(u5u4) 6= 3.
Entonces C(u5u4) = 2 esto forza a que C(u6u5) = 3 (ver figura 1.8). Por consiguiente las
aristas {C(u9u6), C(u8u6)} ⊆ {1, 2}.
Figura 1.8: C(u5u4) = 2 y C(u6u5) = 3.
Veamos el siguiente subcaso:
Subcaso 1.i.- C(u8u6) 6= 1.
Entonces C(u8u6) = 2 (ver figura 1.9).
Figura 1.9: C(u8u6) = 2.
Notemos que para la arista u9u6, C(u9u6) = 1 ya que las aristas adyacentes u6u5 y u8u6 son
1.2. COLORACIÓN POR ARISTAS Y LA GRÁFICA DE PETERSEN 19
coloreadas de tal forma que C(u6u5) = 3 y C(u8u6) = 2.
Como C(u8u2) ∈ {1, 2}, este caso implica que C(u8u2) = 1. Aśı, C(u3u2) = 2 ya que sus aris-
tas adyacentes u8u2 y u2u1 tienen por colores 1 y 3 respectivamente, por lo que C(u4u3) ∈ {1, 3}
(ver figura 1.9).
Ahora bien si suponemos que C(u4u3) 6= 1, entonces C(u4u3) = 3 (ver figura 1.10). Es-
to forza a que las aristas u10u4 y u9u3 sean coloreadas con C(u10u4) = C(u9u3) = 1. Pero
C(u9u6) = 1 lo que es una contradicción al hecho de ser C una 3-coloración propia por aristas.
Figura 1.10: C(u9u6) = C(u9u3) = 1 contradice al hecho de ser C una 3-coloración propia.
La contradicción vino de suponer que C(u4u3) 6= 1, entonces concluimos que C(u4u3) = 1
(ver figura 1.11).
Esto implica que C colorea a las aristas u10u4 y u9u3 como C(u10u4) = C(u9u3) = 3 por que
las aristas adyacentes u5u4 y u3u2 son coloreadas con el color 2, por otra parte C(u9u6) = 1 ya
que la aristas adyacentes u8u6 y u9u3 tienen por color 2 y 3 respectivamente.
Figura 1.11: La arista u9u7 no puede ser coloreada con 1,2 y 3.
20 CAPÍTULO 1. PRELIMINARES.
Lo anterior implica que para la arista u9u7, no puede tener los colores C(u9u7) /∈ {1, 2, 3}
(ver figura 1.11), ya que las aristas adyacentes tienen color C(u9u6) = 1, C(u7u1) = 2 y
C(u9u3) = 3 contradiciendo al hecho de ser C una 3-coloración propia por aristas.
Esto sucedió a partir de suponer que C(u8u6) = 2, entonces veamos el siguiente subcaso.
Subcaso 1.ii.- C(u8u6) 6= 2.
Entonces C(u8u6) = 1 (ver figura 1.12), notemos que la arista u8u2 tiene las siguientes po-
sibilidades C(u8u2) ∈ {1, 2} pero como u8u2 es adyacente a u8u6 ésto forza a que C(u8u2) = 2.
Ahora fijémonos en la arista u3u2 y está tiene como posibilidades C(u3u2) ∈ {1, 2, 3} pe-
ro como las aristas adyacentes a está tienen C(u8u2)=2 y C(u2u1) = 3 ésto que forzaa que
C(u3u2) = 1.
Notemos que para la arista u4u3 tiene las siguientes posibilidades C(u4u3) ∈ {1, 2, 3} pero
las aristas adyacentes a ella tienen C(u3u2) = 1 y C(u5u4) = 2 ésto forza a que C(u4u3) = 3.
Por otra parte la arista u10u8 tiene C(u10u8) = 3 ya que las aristas adyacentes a ella tienen
C(u8u6) = 1 y C(u8u2) = 2.
Por último observemos que para la arista u10u7 tiene C(u10u7) = 1 ya que a las aristas
adyacentes u7u1 y u10u8 tienen color 2 y 3 respectivamente.
Notemos que la arista u10u4 no puede tener C(u10u4) /∈ {1, 2, 3} porque sus aristas adyacen-
tes u10u7,u5u4 y u4u3 tienen por color C(u10u7) = 1, C(u5u4) = 2 y C(u4u3) = 3. Contradiciendo
el hecho de ser C una 3-coloración propia por aristas.
Figura 1.12: La arista u10u4 no puede ser coloreada con 1,2 y 3.
Como la contradicción vino de suponer C(u5u4) = 2, entonces concluimos que C(u5u4) 6= 2,
consideremos la siguiente posibilidad.
Caso 2.- C(u5u4) = 3.
Esto implica que la arista u6u5 tiene color C(u6u5) = 2 (ver figura 1.13), ya que sus aristas
adyacentes u5u1 y u5u4 tienen color 1 y 3 respectivamente.
1.2. COLORACIÓN POR ARISTAS Y LA GRÁFICA DE PETERSEN 21
Figura 1.13: C(u6u5) = 2.
Como C(u8u2) ∈ {1, 2} consideremos los siguientes subcasos.
Subcaso 2.i.- C(u8u2) = 1.
Para este caso C(u3u2) = 2 (ver figura 1.14), ya que la arista u3u2 es adyacente a las aristas
u2u1 y u8u2 que tienen colores 3 y 1 respectivamente. Esto a la vez forza que C(u4u3) = 1 ya
que es adyacente a las aristas u3u2 y u4u5 que tiene color 2 y 3 respectivamente ésto implica que
C(u10u4) = 2 ya que sus aristas adyacentes u4u3 y u5u4 tienen por color 1 y 3 respectivamente.
Esto forza a que C(u10u8) = 3 ya que sus aristas adyacentes u10u4 y u8u2 tienen por color 2 y
1.
Figura 1.14: La arista u8u6 no puede ser coloreada con 1,2 y 3.
Notemos ahora que C(u8u6) /∈ {1, 2, 3} porque las aristas adyacentes a u8u6 son u8u2,u6u5
y u10u8 que tienen colores 1, 2 y 3 respectivamente, lo que contradice el hecho de ser C una
3-coloración propia por aristas (ver figura 1.14).
22 CAPÍTULO 1. PRELIMINARES.
Subcaso 2.ii.- C(u8u2) = 2.
Para este caso tenemos C(u3u2) = 1 (ver figura 1.15), ya que sus aristas adyacentes u8u2
y u2u1 tienen por color 2 y 3 respectivamente, lo que a la vez obliga a que C(u4u3) = 2 ya
que sus aristas adyacentes u3u2 y u5u4 tienen colores 1 y 3 respectivamente; lo que obliga a
C(u10u4) = 1, aśı C(u10u8) = 3 ya que tiene por aristas adyacentes u10u4 y u8u2 que tienen por
color 1 y 2 respectivamente.
Notemos que la arista u10u7 tiene por aristas adyacentes a u10u4,u7u1 y u10u8 que tienen
por color 1,2 y 3 respectivamente, lo que implica que C(u10u7) /∈ {1, 2, 3} lo que contradice al
hecho de que C es una 3-coloración propia por aristas.
Figura 1.15: La arista u10u7 no puede ser coloreada con 1,2 y 3.
Por lo tanto, 4 ≤ χ′(P ) y como anteriormente dimos una 4-coloración propia por aristas de
P se cumple que 4 ≤ χ′(P ) ≤ 4. Aśı χ′(P ) = 4.
Caṕıtulo 2
Coloración arcóıris en gráficas
En este caṕıtulo se dan todas las definiciones necesarias para el tema principal de la tesis.
Iniciamos con los conceptos de camino arcóıris, trayectoria arcóıris, a partir de ello definimos
conexidad arcóıris lo que nos permite hablar de una k-coloración arcóıris de las aristas de una
gráfica G para después introducir los temas de la coloración arcóıris y la fuerte coloración ar-
cóıris para después hablar de rc(G) y src(G) que son los mı́nimos enteros que nos permite tener
una coloración o fuerte coloración arcóıris.
Mostramos la relación entre los enteros rc(G) y src(G) para cualquier gráfica, en particular
para la gráfica de Petersen. Determinamos como obtener el rc(G) y src(G) de gráficas como
los ciclos, ruedas, bipartitas completas, entre otras.
23
24 CAPÍTULO 2. COLORACIÓN ARCOÍRIS EN GRÁFICAS
Definición 2.1. Sean G una gráfica, con al menos una arista y C : A(G)→ {1, 2, · · · , k} con
k ∈ N. Decimos que C es una k-coloración de las aristas de G.
Definición 2.2. Sean G una gráfica, W un camino en G y C : A(G) → {1, 2, · · · , k} una
k-coloración de las aristas de G. Decimos que W es un camino arcóıris si cualesquiera dos
aristas de W tienen asignado un color distinto.
Definición 2.3. Sean G una gráfica, T una trayectoria en G y C : A(G)→ {1, 2, · · · , k} una
k-coloración de las aristas de G. Decimos que T es una trayectoria arcóıris si cualesquiera
dos aristas de T tienen asignado un color distinto.
A continuación damos un ejemplo de las definiciones anteriores.
Figura 2.1: Una grafica G y C una 4-coloración de las aristas de G.
Para los vértices v1 y v5 de la gráfica G, un camino arcóıris entre ellos es el siguiente
W1 = (v1, v2, v3, v1, v5) ya que C(v1v2) = 1, C(v2v3) = 2, C(v3v1) = 3 y C(v1v5) = 4, es decir,
las aristas del camino W1 no repiten color, mientras que para W2 = (v1, v2, v6, v5) otro v1v5-
camino no es arcóıris ya que para las aristas v1v2 y v6v5 se tiene que C(v1v2) = C(v6v5) = 1, es
decir, existe un par de arista en el camino W2 que repiten color.
Para los vértices v1 y v5 una trayectoria arcóıris entre ellos es T = (v1v5), observemos que
es la única ya que para cualquier otra v1v5-trayectoria distinta a T no es arcóıris (ver figura 2.1).
El siguiente teorema nos permitirá trabajar con trayectorias arcóıris en lugar de caminos
arcóıris, ésto nos facilitará en el desarrollo del tema.
Teorema 2.1. Si G es una gráfica, C : A(G)→ {1, 2, · · · , k} es una k-coloración de las aristas
de G y {u, v} ⊆ V (G), entonces todo uv-camino arcóıris contiene una uv-trayectoria arcóıris.
Demostración. Sea W un uv-camino arcóıris de G. Sabemos que todo xy-camino contiene una
xy-trayectoria, en particular W contiene una uv-trayectoria T . Como W es un camino arcóıris
tenemos que cualquier par de aristas de W tienen un color distinto, por lo cual todas las aristas
de T tienen asignado un color distinto. Por lo tanto, tenemos que T es una uv-trayectoria
arcóıris.
Definición 2.4. Sean G una gráfica y C : A(G)→ {1, 2, · · · , k} una k-coloración de las aristas
de G, si G contiene una uv-trayectoria arcóıris para cada par de vértices u y v de G, entonces
decimos que G es conexa arcóıris.
Notemos que a partir de la definición anterior, para que una gráfica sea conexa arcóıris, la
definición implica que, en particular, dicha gráfica debe ser conexa.
25
Definición 2.5. Si G una gráfica y C : A(G) → {1, 2, · · · , k} una k-coloración de las aristas
de G que hace a G conexa arcóıris, entonces C es llamada una k-coloración arcóıris de G.
A continuación damos un ejemplo para identificar estos conceptos.
Figura 2.2: Una gráfica H, C una 2-coloración arcóıris de las aristas de H.
Veamos que C es una 2-coloración arcóıris de la gráfica H, es decir, exhibiremos que para
todo {u, v} ⊆ V (H) existe una uv-trayectoria arcoiŕıs.
Demostración. Observemos que para los vértices que son adyacente en H siempre es posible
encontrar una trayectoria arcóıris entre ellos. Consideremos a los vértices que no son adyacen-
tes, para los vértices v1 y v4 la trayectoria (v1, v6, v4) es una v1v4-trayectoria arcóıris ya que
C(v1v6) = 2 y C(v6v4) = 1, para los vértices v1 y v5 la trayectoria (v1, v2, v5) es una v1v5-
trayectoria arcóıris la razón es que C(v1v2) = 1 y C(v2v5) = 2, para v1 y v4 la trayectoria
(v1, v6, v4) es una v1v4-trayectoria arcóıris porque C(v1v6) = 2 y C(v6v4) = 1.
Ahora para los vértices v2 y v3 la trayectoria (v2, v5, v3) es una v2v3-trayectoria arcóıris ya
que C(v2v5) = 2 y C(v5v3) = 1, por último para los vértices v2 y v6 la trayectoria (v2, v1, v6)
es una v2v6-trayectoria arcóıris ya que C(v2v1) = 1 y C(v1v6) = 2. Por lo tanto, C es una
2-coloración arcóıris. Aśı, H es conexa arcóıris.
En el primer caṕıtulo vimos el concepto de la coloración propia por aristas, la pregunta
ahora es: ¿existe una relación entre la coloración propia y la coloración arcóıris?, a continuación
damos respuesta a esta interrogante.Una coloración arcóıris no necesariamente implica una coloración propia por aristas ya que
en la figura 2.2 para la gráfica H se muestra a C una 2-coloración arcóıris de las aristas de H,
pero para las aristas adyacentes v1v2 y v2v3 se tiene que C(v1v2) = C(v2v3), por lo que C no es
una coloración propia.
Una coloración propia no necesariamente implica una coloración arcóıris, consideremos el
siguiente ejemplo.
26 CAPÍTULO 2. COLORACIÓN ARCOÍRIS EN GRÁFICAS
Figura 2.3: Una gráfica G, C
′
una 2-coloración propia de G
Mostraremos que C
′
es una 2-coloración propia, para esto exhibiremos que para cualesquiera
{a, f} ⊆ A(G) con a adyacente a f cumple con C ′(a) 6= C(f).
Demostración. Notemos que en la gráfica G la arista v1v2 es adyacente a v2v3 con C(v1v2) = 1
y C(v2v3) = 2, aśı C(v1v2) 6= C(v2v3), para la arista v2v3 es adyacente a v3v4 y C
′
(v3v4) = 1,
aśı C
′
(v2v3) 6= C
′
(v3v4). Por lo tanto, C
′
es una 2-coloración propia de las aristas de G.
Notemos que C
′
no es una 2-coloración arcóıris ya que para los vértice v1 y v4 no existe una
v1v4-trayectoria arcóıris porque C
′
(v1v2) = C
′
(v3v4).
Observación 2.1. Dada una gráfica conexa G, siempre es posible dar una coloración arcóıris a
sus aristas. Dicha coloración consiste en asignarle a cada arista de la gráfica un color distinto.
A tal coloración le llamaremos la coloración trivial.
Como siempre es posible asignar una coloración arcóıris a G, entonces ésto nos lleva a la
siguiente definición.
Definición 2.6. Sea G una gráfica. Al mı́nimo natural k para el cual existe una k-coloración
arcóıris de las aristas de G, lo denotamos por rc(G).
Observación 2.2. La coloración arcóıris de la gráfica G que utiliza rc(G) colores es llamada
la mı́nima coloración arcóıris de G.
Definición 2.7. Sean G una gráfica, y C : A(G)→ {1, 2, · · · , k} una k-coloración arcóıris. G
es fuerte conexa arcóıris si G contiene una uv-geodésica arcóıris para cada par de vértices
u y v de G.
Definición 2.8. Sean G una gráfica y C : A(G) → {1, 2, 3, . . . , k}. Si G es fuerte conexa ar-
cóıris, entonces a la coloración C de las aristas de G se le conoce como una fuerte coloración
arcóıris de G.
Definición 2.9. Sea G una gráfica. Al mı́nimo k ∈ N para el cual existe una fuerte coloración
arcóıris de G es denotado por src(G).
Observación 2.3. Una fuerte coloración arcóıris de G que utiliza src(G) colores es llamada
la mı́nima fuerte coloración arcóıris de la gráfica G.
2.1. PRIMEROS RESULTADOS 27
2.1. Primeros resultados
En esta sección se muestra un resultado básico para rc(G) y src(G) y calculamos estos
parámetros en la gráfica de Petersen.
Teorema 2.2. Si G es una gráfica conexa de tamaño m, entonces se cumple la siguiente
desigualdad:
diám(G) 6 rc(G) 6 src(G) 6 m.
Demostración. Demostraremos que diám(G)6 rc(G).
Sean C una mı́nima k-coloración arcóıris de las aristas de la gráfica G, {u, v} ⊆ V (G) tal que
diám(G) = d(u, v) y P una uv-trayectoria arcóıris.
Observemos que por definición de distancia d(u, v) 6 l(P ). Además, por ser C una k-
coloración arcóıris l(P ) 6 k (porque cada color en las aristas de P es distinto), entonces
l(P ) 6 rc(G). Por lo tanto, d(u, v) 6 l(P ) 6 rc(G) y diám(G) = d(u, v) 6 l(P ) 6 rc(G). Aśı,
diám(G) 6 rc(G).
Demostraremos que rc(G) 6 src(G).
Sea C una mı́nima fuerte coloración arcóıris de G. Mostraremos que C es una coloración arcóıris
de G. Como C es una mı́nima fuerte coloración arcóıris de G tenemos que para cualesquiera
{u, v} ⊆ V (G) existe una uv-geodésica arcóıris digamos P , tal que l(P ) = d(u, v). En particular
P es una trayectoria arcóıris para u y v. Por lo tanto, C es una coloración arcóıris para G y como
rc(G) es el mı́nimo k para el cual existe una k-coloración arcóıris tenemos que rc(G) 6 src(G).
Demostraremos que src(G) 6 m.
Sabemos que siempre se le puede dar una coloración arcóıris a la gráfica G, en particular la
trivial, es decir, darle una m-coloración arcóıris donde a cada arista de G se le asigne un color
distinto por lo cual ésta seŕıa una fuerte coloración arcóıris de G, en particular src(G) 6 m.
A continuación damos un ejemplo que nos ayudara a identificar estos conceptos.
En la figura 2.4 se muestra a la gráfica de Petersen, la cual es denotada por P .
Figura 2.4: Una 3-coloración arcóıris y una 4-fuerte coloración arcóıris para P .
28 CAPÍTULO 2. COLORACIÓN ARCOÍRIS EN GRÁFICAS
Hemos visto que a la gráfica de Petersen se le puede dar una 3-coloración arcóıris, ahora
afirmamos que rc(P ) = 3 (ver figura 2.4).
Para esto es necesario notar lo siguiente:
1. La gráfica de Petersen es 3-regular.
2. Para todo {u, v} ⊆ V (P ) tenemos d(u, v) 6 2.
3. Si d(u, v) = 2, entonces existe una única trayectoria de longitud 2 entre los vértices u y
v.
Demostraremos la segunda y tercera observación.
Demostración. A partir de la matriz de adyacencia de P obtenemos A2[P ] que muestra todas
los caminos de longitud 2 en la gráfica de Petersen.
A[P ] =

v1 v2 v3 v4 v5 v6 v7 v8 v9 v10
v1 0 1 0 0 0 1 0 0 1 0
v2 1 0 1 0 0 0 1 0 0 0
v3 0 1 0 1 0 0 0 0 0 1
v4 0 0 1 0 1 0 0 0 1 0
v5 0 0 0 1 0 1 1 0 0 0
v6 1 0 0 0 1 0 0 0 0 1
v7 0 1 0 0 1 0 0 1 0 0
v8 0 0 0 0 0 0 1 0 1 1
v9 1 0 0 1 0 0 0 1 0 0
v10 0 0 1 0 0 1 0 1 0 0

A2[P ] =

v1 v2 v3 v4 v5 v6 v7 v8 v9 v10
v1 3 0 1 1 1 0 1 1 0 1
v2 0 3 0 1 1 1 0 1 1 1
v3 1 0 3 0 1 1 1 1 1 0
v4 1 1 0 3 0 1 1 1 0 1
v5 1 1 1 0 3 0 0 1 1 1
v6 0 1 1 1 0 3 1 1 1 0
v7 1 0 1 1 0 1 3 0 1 1
v8 1 1 1 1 1 1 0 3 0 0
v9 0 1 1 0 1 1 1 0 3 1
v10 1 1 0 1 1 0 1 0 1 3

Observemos que a partir de las matrices anteriores y del corolario 1.1 se tiene que para todo
{u, v} ⊆ V (P ), con u 6= v, se cumple d(u, v) ≤ 2. Además, si d(u, v) = 2, entonces existe una
única trayectoria de longitud 2.
Demostraremos que rc(P ) = 3. En la figura 2.4 se da una 3-coloración arcóıris de la gráfica
de Petersen. Por lo tanto, rc(P ) ≤ 3. Falta ver que 3 ≤ rc(P ).
Supongamos lo contrario, es decir, rc(P ) ≤ 2. Sea C una 2-coloración arcóıris de las aristas
de P . Afirmamos que existen dos aristas adyacentes con el mismo color en P .
Sea v ∈ V (P ), consideremos dos casos sobre v.
2.1. PRIMEROS RESULTADOS 29
Caso 1.- Todas las aristas que inciden en v tienen asignado el mismo color.
Por lo tanto existen dos aristas adyacentes con la misma coloración.
Caso 2.- Existe {ev, fv} ⊆ A(P ) aristas que inciden en v tal que C(ev) 6= C(fv).
Como la gráfica de Petersen es 3-regular implica que δ(v) = 3, entonces existe av una
arista que incide en v tales que av 6= ev y av 6= fv. Como C es una 2-coloración implica que
C(av) = C(ev) ó C(av) = C(fv). Por lo tanto, existen dos aristas adyacentes con la misma
coloración.
Sin pérdida de generalidad, supongamos uv y vw son las aristas adyacentes tales que
C(uv) = C(vw). Ahora, como existe una única trayectoria de longitud 2 en P para cada
par de vértices no adyacentes, la uw-trayectoria (u, v, w) no es una trayectoria arcóıris contra-
diciendo el hecho de que C es una 2-coloración arcóıris de la gráfica de Petersen. Por lo tanto,
rc(P ) 6= 2. Entonces 3 ≤ rc(P ) ≤ 3, aśı rc(P ) = 3.
A partir de que rc(P ) = 3 y de la desigualdad dada en el teorema 2.2 sabemos que
src(P ) ≥ 3.
Ahora veamos que src(P ) = 4.
Como en la figura 2.4 se muestra una 4-fuerte coloración arcóıris de las aristas de P se tiene
que src(P ) ≤ 4. Mostraremos que 4 ≤ src(P ). Procederemos por contradicción, es decir,
supongamos que src(P ) = 3 entonces existe C
′
una 3-fuerte coloración arcóıris de las aristas de
P . Como χ
′
(P ) = 4, entonces al menos dos aristas adyacentes de P son coloreadas con el mismo
color ya que estamos utilizando menos colores que χ
′
(P ) = 4. Supongamos que uv y vw son
estas aristas. Aśı, T = (u, v, w) es una uw-trayectoria de longitud 2 lo que implica que es una
uw-geodésica y además, es única. Por lo tanto, T no es una geodésicaarcóıris de los vértices v
y w ya que para las aristas uv y vw son coloreadas con el mismo color contradiciendo el hecho
de que C
′
es una 3-fuerte coloración arcóıris de las aristas de P . Por lo tanto, 4 ≤ src(P ) ≤ 4.
Aśı, src(P ) = 4.
Veamos otro ejemplo en el que se muestra la igualdad, consideremos la gráfica G de la figura
2.5, donde se muestra a C : A(G) → {1, 2, 3, 4} una mı́nima 4-fuerte coloración arcóıris y que
a la vez es una mı́nima coloración arcoŕıs de las aristas de G.
Figura 2.5: Una gráfica G con rc(G) = src(G) = 4.
30 CAPÍTULO 2. COLORACIÓN ARCOÍRIS EN GRÁFICAS
Primero mostraremos que la coloración que se presenta en la figura 2.5 es en efecto una
fuerte coloración arcóıris:
Para esto observemos lo siguiente:
Observación 2.4. Para cualquier par de vértices {u, v} ∈ V (G) existe una uv-geodésica ar-
cóıris en G.
Obtengamos las geodésicas arcóıris para el vértice u:
Para los vértices u y u1: la trayectoria (u, u1) es una geodésica arcóıris. Para los vértices u
y v1: la trayectoria (u, u1, v1) es una geodésica arcóıris. Para los vértices u y v: la trayectoria
(u, u1, v1, v) es una geodésica arcóıris. Para los vértices u y v2: la trayectoria (u, u2, v2) es una
geodésica arcóıris. Para los vértices u y u2: la trayectoria (u, u2) es una geodésica arcóıris. Para
los vértices u y v3: la trayectoria (u, u3, v3) es una geodésica arcóıris. Para los vértices u y u3:
la trayectoria (u, u3) es una geodésica arcóıris.
Obtengamos las geodésicas arcóıris para el vértice u1:
Para los vértices u1 y v1: la trayectoria (u1, v1) es una geodésica arcóıris. Para los vértices u1
y v: la trayectoria (u1, v1, v) es una geodésica arcóıris. Para los vértices u1 y v2: la trayectoria
(u1, u, u2, v2) es una geodésica arcóıris. Para los vértices u1 y u2: la trayectoria (u1, u, u2) es
una geodésica arcóıris. Para los vértices u1 y v3: la trayectoria (u1, v1, v, u3) es una geodésica
arcóıris. Para los vértices u1 y u3: la trayectoria (u1, u, u3) es una geodésica arcóıris.
Obtengamos las geodésicas arcóıris para el vértice v1:
Para los vértices v1 y v: la trayectoria (v1, v) es una geodésica arcóıris. Para los vértices v1 y
v2: la trayectoria (v1, v, v2) es una geodésica arcóıris. Para los vértices v1 y u2: la trayectoria
(v1, u1, u, u2) es una geodésica arcóıris. Para los vértices v1 y v3: la trayectoria (v1, v, v3) es una
geodésica arcóıris. Para los vértices v1 y u3: la trayectoria (v1, u1, u, u3) es una geodésica arcóıris.
Obtengamos las geodésicas arcóıris para el vértice v:
Para los vértices v y v2: la trayectoria (v, v2) es una geodésica arcóıris. Para los vértices v y u2: la
trayectoria (v, v2, u2) es una geodésica arcóıris. Para los vértices v y v3: la trayectoria (v, v3) es
una geodésica arcóıris. Para los vértices v y u3: la trayectoria (v, v3, u3) es una geodésica arcóıris.
Obtengamos las géodesicas arcóıris para el vértice v2:
Para los vértices v2 y u2: la trayectoria (v2, u2) es una geodésica arcóıris. Para los vértices v2
y v3: la trayectoria (v2, v, v3) es una geodésica arcóıris. Para los vértices v2 y u3: la trayectoria
(v2, u2, u, u3) es una geodésica arcóıris.
Obtengamos las geodésicas arcóıris para el vértice u2:
Para los vértices u2 y u3: la trayectoria (u2, u, u3) es una geodésica arcóıris. Para los vértices
u2 y v3: la trayectoria (u2, u, u3, v3) es una geodésica arcóıris.
Por último, para los vértices v3 y u3 tenemos que la trayectoria (v3, u3) es una geodésica
arcóıris.
Por lo tanto, la coloración que se muestra en la figura 2.5 es una 4-fuerte coloración arcóıris
de G. Aśı src(G) ≤ 4.
2.1. PRIMEROS RESULTADOS 31
Ahora observemos que diám(G) ≥ 3. Para esto obtengamos todas las excentricidades de los
vértices de G:
La excentricidad del vértice u es e(u) = 3, donde: d(u, u1) = d(u, u2) = d(u, u3) = 1,
d(u, v1) = d(u, v2) = d(u, v3) = 2 y d(u, v) = 3.
La excentricidad del vértice u1 es e(u1) = 3, ya que si obtenemos d(u1, u) = d(u1, v1) = 1,
d(u1, v) = d(u1, u2) = d(u1, u3) = 2 y d(u1, v2) = d(u1, v3) = 3.
La excentricidad del vértice v1 es e(v1) = 3, ya que si obtenemos d(v1, v) = d(v1, u1) = 1,
d(v1, v2) = d(v1, v3) = d(v1, u) = 2 y d(v1, u2) = d(v1, u3) = 3.
La excentricidad del vértice v es e(v) = 3, donde: d(v, v2) = d(v, v3) = d(v, v1) = 1,
d(v, u2) = d(v, u3) = d(v, u1) = 2 y d(v, u) = 3.
La excentricidad del vértice v2 es e(v2) = 3, ya que si obtenemos d(v2, v) = d(v2, u2) = 1,
d(v2, u) = d(v2, v1) = d(v2, v3) = 2 y d(v2, u1) = d(v2, u3) = 3.
La excentricidad del vértice u2 es e(u2) = 3, ya que si obtenemos d(u2, u) = d(u2, v2) = 1,
d(u2, u1) = d(u2, v) = d(u2, u3) = 2 y d(u2, v1) = d(u2, v3) = 3.
La excentricidad del vértice v3 es e(v3) = 3, ya que si obtenemos d(v3, u3) = d(v3, v) = 1,
d(v3, u) = d(v3, v1) = d(v3, v2) = 2 y d(v3, u1) = d(v3, u2) = 3.
La excentricidad del vértice u3 es e(u3) = 3, ya que si obtenemos d(u3, u) = d(u3, v3) = 1,
d(u3, u1) = d(u3, v) = d(u3, u2) = 2 y d(u3, v1) = d(u3, v2) = 3.
Por lo que el diámetro de la gráfica es diám(G) = máx{e(v)|v ∈ V (G)} = 3.
Observemos también que para la gráfica G se cumple:
Observación 2.5. Para {x, y} ⊆ V (G) tal que d(x, y) = 2, G contiene exactamente una
xy-trayectoria de longitud 2.
Demostración. Supongamos que la xy-trayectoria de longitud 2 no es única, es decir, existen:
T1 = (x,w, y) una xy-trayectoria y T2 = (x,w
′
, y) otra xy-trayectoria con w 6= w′ . Ahora, bien
sea C = (x,w, y, w
′
, x) un ciclo. Por lo tanto, en G existe un ciclo de longitud 4 pero esto no es
posible ya que en G no hay ciclos de longitud 4. Por lo tanto, en G las trayectorias de longitud
2 son únicas.
Por lo anterior, sabemos que la gráfica G cumple que diám(G) = 3 y src(G) ≤ 4. Mostra-
remos que rc(G) = src(G) = 4.
Demostración. A partir de que diám(G) = 3, se sigue por el teorema 2.2 que rc(G) ≥ 3.
Afirmamos que rc(G) = 4. Supongamos lo contrario, rc(G) = 3. Entonces existe C
′
una
3-coloración arcóıris de las aristas de G.
Para los vértices {u, v} ⊆ V (G) todas las uv-trayectorias en la gráfica G tienen longitud 3,
al menos una de estas uv-trayectorias tiene que ser una trayectoria arcóıris (ver figura 2.5). Sin
32 CAPÍTULO 2. COLORACIÓN ARCOÍRIS EN GRÁFICAS
pérdida de generalidad asumamos que (u, u1, v1, v) es la trayectoria arcóıris, tal que la coloración
de las aristas esta dada por C
′
(uu1) = 1, C
′
(u1v1) = 2 y por último C
′
(v1v) = 3 (ver figura 2.6).
Figura 2.6: La gráfica G suponiendo que C
′
(uu1) = 1, C
′
(u1v1) = 2 y C
′
(v1v) = 3.
Ahora para cualesquiera x y y vértices de G tales que d(x, y) = 2, se tiene de la observación
anterior que existe una única xy-trayectoria, y por ser C
′
una coloración arcóıris, dicha trayec-
toria es una xy-trayectoria arcóıris. Por lo tanto, para la arista uu2 tiene dos posibilidades en
su color: C
′
(uu2) = 2 ó C
′
(uu2) = 3. Consideremos los siguiente casos.
Caso 1.- C
′
(uu2) = 2.
Para este caso tenemos que C
′
(uu3) = 3. Por lo tanto, {C
′
(vv2), C
′
(vv3)} = {1, 2}, conside-
remos los siguientes subcasos.
Subcaso 1.i.- C
′
(vv2) = 1.
Para este subcaso se tiene que C
′
(vv3) = 2 y C
′
(u2v2) = 3 y C
′
(u3v3) = 1. En este caso
tenemos que para {u1, v3} ⊂ V (G) no existe una u1v3-trayectoria arcóıris, contradiciendo el
hecho de que C
′
es una coloración arcóıris.
Subcaso 1.ii.- C
′
(vv2) = 2.
Implicaŕıa que C
′
(vv3) = 1 y C
′
(v3u3) = 2. Por lo tanto, para C
′
(v2u2) ∈ {1, 3}, si
C
′
(v2u2) = 1 entonces para {u2, v3} ⊂ V (G) no existe una u2v3-trayectoria arcóıris, ahora
si C
′
(v2u2) = 3 esto implicaŕıa que {u2, v1} ⊂ V (G) no existe una u2v1-trayectoria arcóıris.
Caso 2.- C
′
(uu2) = 3 .
Para este caso procedemos de forma análoga al caso 1.
Por lo tanto, no existe una 3-coloración arcóıris de las aristas de G. Recordemos que ya dimos
una 4-fuerte coloración arcóıris de las aristas de G (Ver figura 2.5), por lo que: por teorema 2.2
setiene que 3 =diám(G) ≤ rc(G) ≤ src(G) ≤ 4 y por afirmación anterior 3 < rc(G) entonces,
rc(G) = src(G) = 4.
2.2. LA MÍNIMA COLORACIÓN ARCOÍRIS Y LA MÍNIMA FUERTE COLORACIÓN ARCOÍRIS33
2.2. La mı́nima coloración arcóıris y la mı́nima fuerte
coloración arcóıris
En esta sección mostramos la relación entre la mı́nima coloración arcóıris y la mı́nima fuerte
coloración arcóıris. Para ello veamos la siguiente proposición.
Proposición 2.1. Si G es una gráfica no trivial, conexa y de tamaño m, entonces.
(a).- src(G) = 1 si y sólo si G es una gráfica completa.
(b).- rc(G) = 2 si y sólo si src(G) = 2.
(c).- rc(G) = m si y sólo si G es árbol.
(d).- rc(G) = 1 si y sólo si src(G) = 1.
Comprobación del inciso (a).
Demostración. Si src(G) = 1, entonces G es una gráfica completa.
Como el src(G) = 1 implica que para todo {u, v} ⊆ V (G) se tiene que uv ∈ A(G). Por lo tanto,
G es una gráfica completa.
Mostremos el rećıproco, si G es una gráfica completa, entonces src(G) = 1.
Como G es una gráfica completa, se tiene que para todo {u, v} ⊆ V (G) existe T una uv-
trayectoria de tal forma que l(T ) = 1. Por lo tanto, T es una uv-geodésica.
Sea C : A(G) → {1} una coloración tal que para toda A ∈ A(G), C(a) = 1. Por lo tanto,
para todo {u, v} ⊆ V (G) existe una uv-geodésica arcóıris. Entonces C es una 1-fuerte coloración
arcóıris de las aristas de G, observemos que es la fuerte coloración mas pequeña. Por lo tanto,
src(G) = 1.
Comprobación del inciso (b).
Demostración. Si src(G) = 2, entonces rc(G) = 2.
Por teorema 2.2 sabemos que rc(G) ≤ src(G) = 2 entonces rc(G) ≤ 2. Por otro lado, del
inciso (a) se tiene que G no es completa. Por lo tanto, existen {u, v} ⊆ V (G) tales que u no
es adyacente a v, entonces para todas las trayectorias entre los vértices u y v se necesitan al
menos dos colores distintos para tener una uv-trayectoria arcóıris. Aśı, 2 ≤ rc(G) ≤ 2. Por lo
tanto, rc(G) = 2.
Mostremos el rećıproco, si rc(G) = 2, entonces src(G) = 2.
Como rc(G) = 2, entonces existe C una 2-coloración arcóıris de las aristas de G. Afirmamos
que C es una 2-fuerte coloración arcóıris. Mostraremos que para todo {u, v} ⊆ V (G) existe una
uv-geodésica arcóıris.
Notemos que si uv ∈ A(G), entonces existe una uv-geodésica arcóıris, por el contrario
si uv /∈ A(G) por ser C una 2-coloración arcóıris, existe T una uv-trayectoria arcóıris tal
que l(T ) = 2, por lo que T es una uv-geodésica arcóıris. Por lo tanto, C es una 2-fuerte
coloración arcóıris, es decir, src(G) ≤ 2. Por la desigualdad del teorema 2.2 tenemos que
2 = rc(G) ≤ src(G) ≤ 2. Por lo tanto, src(G) = 2.
Comprobación del inciso (c).
34 CAPÍTULO 2. COLORACIÓN ARCOÍRIS EN GRÁFICAS
Demostración. Si rc(G) = m, entonces la gráfica G es un árbol. Equivalentemente a que si G
no es árbol entonces rc(G) 6= m.
Afirmamos que si G no es árbol entonces rc(G) ≤ m− 1.
Supongamos que G no es un árbol, entonces G contiene un ciclo γk = (v1, v2, . . . , vk = v1) donde
k ≥ 3. Sea C : A(G)→ {1, 2, . . . ,m−1} una coloración de las aristas de G tal que C(v1v2) = 1 ,
C(v2v3) = 1 y para el resto de las aristas asignamos los m−2 colores restantes {2, 3, . . . ,m−1}.
Primero mostraremos que C es una (m− 1)-coloración arcóıris de las aristas de G.
Para demostrar esta afirmación nos apoyaremos en la gráfica G\(v1v2) ya que tiene la propiedad
de V (G \ (v1v2)) = V (G), por teorema 1.2, G \ (v1v2) es una gráfica conexa de tamaño m− 1.
Esto implica que para todo {u, v} ⊆ V (G \ (v1v2)) = V (G) existe una uv-trayectoria, además
como C(v1v2) = C(v2v3) y v1v2 /∈ A(G \ (v1v2)) entonces G \ (v1v2) es conexa arcóıris, es decir,
C es una (m− 1)-coloración arcóıris de G \ (v1v2) y de G. Por lo tanto rc(G) ≤ m− 1.
Mostraremos el rećıproco, si G es árbol, entonces rc(G) = m.
Se procederá por reducción al absurdo. Sea G un árbol de tamaño m y supondremos que
rc(G) ≤ m− 1. Por ser rc(G) ≤ m− 1, existe C una (m− 1)-coloración arcóıris de las aristas
de G, como el tamaño de G es m y estamos utilizando m − 1 colores, implica que existen dos
aristas en G que tienen asignado el mismo color. Sea e = uv y f = xy estas aristas, tal que
C(e) = C(f). Consideremos el orden de aparición de los vértices u y y con respecto a una
trayectoria T que contenga a las aristas e y f .
Caso 1.- T = (u, v, . . . , x, y).
Para este caso consideramos z = u y w = y. Aśı, la zw-trayectoria no es arcóıris ya que
C(e) = C(f).
Caso 2.- T = (u, v, . . . , y, x).
Para este casos consideramos z = u y w = x. Aśı, la zw-trayectoria no es arcóıris ya que
C(e) = C(f) y C(f) = C(xy) = C(yx).
Caso 3.- T = (v, u, . . . , y, x).
Para este caso consideramos z = v y w = x. Aśı, la zw-trayectoria no es arcóıris ya que
C(e) = C(f) donde C(e) = C(uv) = C(vu) y C(f) = C(xy) = C(yx).
Caso 4.- T = (v, u, . . . , x, y).
Para este caso consideramos z = v y w = y. Aśı, la zw-trayectoria no es arcóıris ya que
C(e) = C(f), donde C(e) = C(uv) = C(vu).
Como G es un árbol, entonces para todo {z, w} ⊆ V (G) la zw-trayectoria es única y por los
casos anteriores, para los vértices z y w no existe una zw-trayectoria arcóıris pero esto contradice
el hecho de que C es una (m−1)-coloración arcóıris. Por lo tanto, m−1 ≤ rc(G) ≤ src(G) ≤ m,
aśı m− 1 < rc(G) ≤ m. Por lo tanto, rc(G) = m.
Comprobación del inciso (d).
2.3. RC(G) Y SRC(G) PARA CICLOS 35
Demostración. Si rc(G) = 1, entonces src(G) = 1.
Como rc(G) = 1 existe C una mı́nima 1-coloración de las aristas de G, es decir, para todo
{u, v} ⊆ V (G) existe una uv-trayectoria arcóıris y como estamos utilizando un color implica
que estas trayectorias son de longitud 1 para cualquier par de vértices, es decir, uv ∈ A(G),
aśı G es completa y por inciso (a) tenemos que src(G) = 1.
Mostremos el reciproco, si src(G) = 1, entonces rc(G) = 1.
Se sigue del inciso (a) que la gráfica G es completa y con un razonamiento análogo al inciso (a)
concluimos que rc(G) = 1.
2.3. rc(G) y src(G) para ciclos
En esta sección mostramos el número de la mı́nima coloración arcóıris y el número de la
mı́nima fuerte coloración arcóıris para ciclos.
Proposición 2.2. Para cada entero n ≥ 4, rc(γn) = src(γn) = dn2 e.
Demostración. Sean γn = (v1, v2, . . . , vn, vn+1 = v1) y ei = vivi+1 ∈ A(γn) con i ∈ {1, . . . , n}.
Consideremos dos casos, cuando n es par y cuando n es impar.
Caso(1).- n = 2k, con k ≥ 2.
Por teorema 2.2 se sabe que diám(γn) ≤ rc(γn) ≤ src(γn) ≤ m. Además, como el diámetro
de un ciclo está determinado por diám(γn) = bn2 c, entonces b
n
2
c = 2k
2
= k. Aśı,
k = bn
2
c ≤ rc(γn) ≤ src(γn) ≤ m. (2.1)
Veremos que existe una k-fuerte coloración arcóıris de las aristas de γn.
Sea C0 : A(γn) → {1, 2, · · · , k} una coloración de las aristas de γn, definida de la siguiente
forma:
C0(ei) =
{
i si 1 ≤ i ≤ k
i− k si k + 1 ≤ i ≤ n.
Figura 2.7: C0 una k-fuerte coloración arcóıris de γn.
36 CAPÍTULO 2. COLORACIÓN ARCOÍRIS EN GRÁFICAS
Observemos que dada la coloración C0, se tiene que para las primeras k aristas {e1, e2, . . . , ek}
son coloreadas con k colores distintos. Ahora bien, las aristas en {ek+1, ek+2, . . . , e2k} son co-
loreados con los mismos k colores, tales que C0(ek+1) = 1, C0(ek+2) = 2, C0(ek+3) = 3 hasta
C0(e2k) = k.
Mostraremos que la coloración C0 es una fuerte coloración arcóıris de las aristas de γn; es
decir, que para todo {u, v} ⊆ V (γn) existe una uv-geodésica arcóıris.
Sea {u, v} ⊆ V (γn). Supongamos sin pérdida de generalidad que u = vj y v = vl, con j < l.
Fijémonos en los vértices v1 y vk+1 aśı como también en las trayectorias P1 = (v1, γn, vk+1) y
P2 = (vk+1, γn, v1) ver figura 2.7. Veamos los siguientes casos:
Subcaso(1.a).- {vj, vl} ⊆ V (P1).
Por ser γn un ciclo tenemos que para vj y vl existen dos trayectorias; T1 = (vj, γn, vl) y
T2 = (vj, γ
−1
n , v1) ∪ P−12 ∪ (vk+1, γ−1n , vl).
Observemos que l(T2) = l(vj, γ
−1
n , v1) + l(P
−1
2 ) + l(vk+1, γ
−1
n , vl) ≥ l(P−12 ) = l(P2), aśı se cumple
l(T2) ≥ l(P2). Por otraparte, T1 ⊆ P1, por lo que l(T1) ≤ l(P1) y recordemos que n es par,
entonces l(P1) = l(P2). Aśı l(T1) ≤ l(P1) = l(P2) ≤ l(T2). Entonces, l(T1) ≤ l(T2). Por lo tanto,
T1 es una vjvl-geodésica.
Recordemos que las primeras k aristas {e1, e2, · · · , ek}, las cuales son aristas de P1, tienen
asignados k colores distintos. Por lo tanto, T1 es una vjvl-geodésica arcóıris.
Para el caso en que {vj, vl} ⊆ V (P2) se procede de manera análoga, por lo que también para
ese caso se encontraŕıa la vjvl-geodésica arcóıris.
Subcaso(1.b).-vj ∈ V (P1) \ {v1, vk+1} y vl ∈ V (P2) \ {v1, vk+1}, donde j < l.
Sin pérdida de generalidad fijemos al vértice vj y tomemos al vértice vj+(k+1), tales que
C0(vj+kvj+(k+1)) = C0(ej+k) = j. Aśı proponemos la trayectoria T3 = (vj, γn, vj+(k+1)). Las
únicas aristas que repiten color en T3 son ej y ej+k, con el color j. Ahora bien, l(T3) = k + 1.
Como γn es un ciclo par de longitud 2k, entonces para la trayectoria T4 = (vj, γ
−1
n , vj+(k+1)),
l(T4) = k − 1. Ver figura 2.8.
Figura 2.8: Subcaso(1.b).
2.3. RC(G) Y SRC(G) PARA CICLOS 37
Veamos los siguientes casos sobre l:
Subcaso(1.b.i).- l = j + (k + 1).
Entonces, la trayectoria T4 es una geodésica. Más aún, es una vjvl-geodésica arcóıris ya
que las aristas {ej+k+1, ej+k+2, . . . , e2k} tienen los colores {j + 1, j + 2, . . . , k} y las aristas
{e1, e2, . . . , ej} tienen asignado los colores {1, 2, . . . , j}.
Subcaso(1.b.ii).- l > j + (k + 1).
Aśı, la trayectoria (vj, γ
−1
n , vl) ⊆ T4, por lo que es una trayectoria arcóıris y notemos que
l((vj, γ
−1
n , vl)) ≤ l(T4) = k − 1 lo que implica que para la otra trayectoria (vj, γn, vl) tiene
longitud l((vj, γn, vl)) > k+ 1. Por lo tanto, la trayectoria (vj, γ
−1
n , vl) es una geodésica arcóıris.
Subcaso(1.b.iii).- l = j + k.
Como las únicas aristas que repiten color en la trayectoria T3 son las aristas ej y ek+j pro-
ponemos a la trayectoria T
′
3 = (vj, γn, vj+k) tales que A(T
′
3) = A(T3) \ {ej+k}. Aśı T
′
3 es una
trayectoria arcóıris. Más aún, como l(T
′
3) = l(T3)− 1 = k y γn es un ciclo par, entonces la tra-
yectoria (vj, γ
−1
n , vj+k) cumple que l((vj, γ
−1
n , vj+k)) = k. Por lo tanto, T
′
3 es una vjvl-geodésica
arcóıris.
Subcaso(1.b.iv).- l < j + k.
Aśı, la trayectoria T
′′
3 = (vj, γn, vl) es tal que T
′′
3 ⊂ T3 y l(T
′′
3 ) < l(T3) = k + 1, por
lo que l(T
′′
3 ) ≤ k. Por lo tanto, T
′′
3 es una geodésica ya que para la otra posible trayectoria
(vj, T4, vj+(k+1)) ∪ (vj+(k+1), γ−1n , vl) tiene longitud al menos k por ser γn un ciclo par.
Observemos que ek+j /∈ A(T
′′
3 ). Aśı T
′′
3 es una vjvl-geodésica arcóıris.
De esta manera, C0 es una k-fuerte coloración arcóıris de las aristas de γn y por la desigual-
dad 2.1 se tiene que k =diám(γn) ≤ rc(γn) ≤ src(γn) ≤ k.
Por lo tanto rc(γn) = src(γn) = k.
Caso(2).- n es impar, n = 2k + 1 para k ≥ 2.
Definamos a C1 : A(γn)→ {1, 2, . . . , k+ 1}, una coloración de las aristas de γn, como sigue:
C1(ei) =
{
i si 1 ≤ i ≤ k + 1
i− (k + 1) si k + 2 ≤ i ≤ n.
Por lo anterior, C1 colorea a las primeras k+ 1 aristas {e1, e2, e3, . . . , ek+1} con k+ 1 colores
tales que cada arista recibe un color distinto.
Observemos que para las k aristas restantes {ek+2, ek+3, . . . , e2k, e2k+1} la asignación es como
sigue: C1(ek+2) = 1, C1(ek+3) = 2, C1(ek+4) = 3 aśı hasta C1(e2k) = k − 1 y C1(e2k+1) = k de
tal forma que las k aristas restantes tienen también un color distinto. Ver figura 2.9.
38 CAPÍTULO 2. COLORACIÓN ARCOÍRIS EN GRÁFICAS
Figura 2.9: C1 una (k + 1)-fuerte coloración arcóıris de γn.
Afirmación.- C1 es una (k + 1)-fuerte coloración arcóıris.
Demostraremos que para todo {u, v} ⊆ V (γn), existe una uv-geodésica arcóıris.
Sea {u, v} ⊆ V (γn). Supongamos sin pérdida de generalidad que u = vj y v = vl con j < l.
Fijémonos en los vértices v1 y vk+2, y en las trayectorias P1 = (v1, γn, vk+2) y P2 = (vk+2, γn, v1),
donde l(P1) = k + 1 y l(P2) = k (ver figura 2.9). Veamos los siguientes casos.
Subcaso(2.a).- {vj, vl} ⊆ V (P1) \ {v1, vk+2}.
Sean T1 = (vj, γn, vl) y T2 = (vj, γ
−1
n , v1) ∪ P−12 ∪ (vk+2, γ−1n , vl) las dos trayectorias entre vj
y vl en γn. Como para este caso {vj, vl} y {v1, vk+2} son ajenos, implica que l((vl, γn, vk+2)) ≥ 1
y que l((v1, γn, vj)) ≥ 1, entonces l(T2) ≥ k + 2 porque l(P2) = k y como T1 ⊆ P1 se tiene que
l(T1) ≤ l(P1) = k + 1. Por lo tanto, l(T1) < l(T2). Aśı, T1 es una vjvl-geodésica; además como
en P1 todas las aristas del conjunto {e1, e2, . . . , ek+1} son coloreados con k+ 1 colores distintos,
entonces T1 es una vjvl-geodésica arcóıris.
Figura 2.10: Subcaso(2.a).
2.3. RC(G) Y SRC(G) PARA CICLOS 39
Subcaso(2.b).- {vj, vl} = {v1, vk+2}.
Las únicas trayectorias entre vj y vl son P1 y P2. Como l(P2) = k < l(P1) = k+ 1 y las aris-
tas de la trayectoria P2 son coloreadas con k colores distintos, entonces P2 es una vjvl-geodésica
arcóıris.
Subcaso(2.c).- {vj, vl} ⊆ V (P2) \ {v1, vk+2}.
Sean T1 = (vj, γn, vl) y T2 = (vj, γ
−1
n , vk+2) ∪ P−11 ∪ (v1, γ−1n , vl). Como T1 ⊆ P2, entonces
l(T1) ≤ l(P2) < l(P1). Por otro lado, con un razonamiento similar al dado en el subcaso 2.a, se
tiene que l(vj, γ
−1
n , vk+2) ≥ 1 y l(v1, γ−1n , vl) ≥ 1 lo que implica que l(T2) ≥ (k + 1) + 2 porque
l(P1) = k + 1. Aśı l(P1) < l(T2), lo que implica que l(T1) < l(T2). Por lo tanto, T1 es una
vjvl-geodésica; más aún, una vjvl-geodésica arcóıris ya que en la trayectoria P2 sus aristas son
coloreadas con k colores distintos.
Figura 2.11: Subcaso(2.c).
Subcaso (2.d).- |{vj, vl} ∩ {v1, vk+2}| = 1.
Consideremos los siguientes subcasos:
Subcaso (2.d.i).- v1 = vj y vl ∈ P1.
Entonces vl 6= vk+2. Sean T1 = (vj, γn, vl) y T2 = P−12 ∪(vk+2, γ−1n , vl) las dos vjvl-trayectorias.
Notemos que l(T2) = l(P
−1
2 ) + l((vk+2, γ
−1
n , vl) y como vl 6= vk+2 entonces 1 ≤ l((vk+2, γ−1n , vl)),
aśı k + 1 ≤ l(T2). Como l(T1) ≤ k, entonces l(T1) < l(T2) aśı T1 es una vjvl-geodésica, además
como T1 ⊆ P1 y en la trayectoria P1 todas las aristas del conjunto {e1, e2, e3, · · · , ek+1} son
coloreadas con k + 1 colores distintos, entonces T1 es una vjvl-geodésica arcóıris.
Subcaso (2.d.ii).- v1 = vj y vl ∈ P2.
Por la suposición del subcaso (2.d) se tiene que vl 6= vk+2. Sean T1 = P1 ∪ (vk+2, γn, vl) y
T2 = (vj, γ
−1
n , vl). Observemos que como P1 ⊆ T1 entonces k+ 1 = l(P1) ≤ l(T1). Por otro lado,
como T2 ⊆ P2, entonces l(T2) ≤ l(P2) = k. Por lo tanto, l(T2) < l(T1), lo que implica que la
trayectoria T2 es una vjvl-geodésica. Como T2 ⊆ P2 y en la trayectoria P2 todas las aristas del
40 CAPÍTULO 2. COLORACIÓN ARCOÍRIS EN GRÁFICAS
conjunto {ek+2, ek+3, · · · , e2k, e2k+1} son coloreadas con k colores distintos, entonces T2 es una
vjvl-geodésica arcóıris.
Subcaso (2.d.iii).- vk+2 = vj y vl ∈ P2.
Sean T1 = (vj, γn, vl) y T2 = P
−1
1 ∪ (v1, γ−1n , vl) las dos vjvl-trayectorias, observemos que
T1 ⊆ P2 lo que implica l(T1) ≤ l(P2) y esto nos lleva a concluir que l(T1) ≤ k. Como
l(P−11 ) = l(P1) = k + 1, entonces k + 1 ≤ l(T2). Aśı l(T1) ≤ l(T2) lo cual nos dice que
T1 es una vjvl-geodésica y como T1 ⊆ P2 y en la trayectoria P2 todas las aristas del conjunto
{ek+2, ek+3, · · · , e2k, e2k+1} son coloreadas con k colores distintos entonces T1 es una vjvl-geodési-
ca arcóıris.
Observemos que no es posible el subcaso en que el vértice vl esté en la trayectoria P1, es
decir, vl ∈ P1 ya que j < l.
Notemos también que para el subcaso en que vl = v1 y vj ∈ P2 es el subcaso (2.d.ii) y para
el subcaso en que vl = v1 y vj ∈ P1 no es posible ya que j < l.
Subcaso (2.d.iv).- vk+2 = vl y vj ∈ P1.
Sean T1 = (vj, γn, vl) y T2 = (vj, γ
−1
n , v1) ∪ P−12 , las dos vjvl-trayectorias. Notemos que
l(T2) = l((vj, γ
−1
n , v1)) + l(P
−1
2 ); además como vk+2 = v1 entonces v1 6= vj lo que implica
1 ≤ l((vj, γ−1n , v1)). Aśı k + 1 ≤ l(T2), y como el ciclo γn es de longitud impar, l(T1) ≤ k. Por
lo tanto, l(T1) < l(T2), aśı T1 es una vjvl-geodésica. Puesto que T1 ⊆ P1 y en la trayectoria P1
todas las aristas del conjunto {e1,e2, e3, · · · , ek+1} son coloreadas con k + 1 colores distintos.
Por lo tanto, T1 es una vjvl-geodésica arcóıris.
Observemos que no es posible el subcaso en que el vértice vj esté en la trayectoria P2, es
decir, vj ∈ P2 ya que j < l.
Subcaso(2.e).- vj ∈ V (P1) \ {v1, vk+2} y vl ∈ V (P2) \ {v1, vk+2}.
Sin pérdida de generalidad dejemos fijo al vértice vj y tomemos al vértice vk+(j+2). Note
que C1(vk+(j+1)vk+(j+2)) = C1(ek+(j+1)) = j. Aśı, la trayectoria P3 = (vj, γn, vk+(j+2)) contiene
únicamente dos aristas que repiten el color j; a saber, ej y ek+(j+1).
Figura 2.12: Subcaso(2.e).
2.3. RC(G) Y SRC(G) PARA CICLOS 41
Ahora bien, l(P3) = j + ((k + 1) − (j − 1)) = k + 2. Como γn es un ciclo de longitud
2k + 1 se tiene que la trayectoria P4 = (vj, γ
−1
n , vk+(j+2)) tiene longitud l(P4) = k − 1. Aho-
ra como en la trayectoria P4 las aristas en el conjunto {ek+(j+2), . . . , e2k+1} tienen los colores
{j + 1, j + 2, · · · , k} y las aristas {e1, e2, . . . , ej} tienen asignado los colores {1, 2, · · · , j}, en-
tonces P4 es una trayectoria arcóıris.
Consideremos los siguientes casos sobre vl.
Subcaso(2.e.i).- l > k + (j + 1).
Sea T1 la trayectoria T1 = (vj, γ
−1
n , vl). Como T1 ⊆ P4, entonces l(T1) ≤ l(P4) < l(P3), de
esta manera T1 es una vjvl-geodésica ya que para la otra trayectoria T2 = P3 ∪ (vk+(j+2), γn, vl)
debe tener longitud mayor o igual a k + 2. Recordemos que T1 ⊆ P4 y como P4 es arcóıris,
entonces T1 es una vjvl-geodésica arcóıris.
Subcaso(2.e.ii).- l = k + (j + 1).
Sean T1 = P4 ∪ (vk+(j+2), vk+(j+1)) y T2 = P3 \ {vk+(j+2)} las dos vjvl-trayectorias. Observe-
mos que l(T1) = l(P4) + l((vk+(j+2), vk+(j+1))) = k, por otro lado l(T2) = l(P3)− 1 = k + 1. Por
lo tanto, l(T1) < l(T2), por lo que T1 es una vjvl-geodésica.
Como las aristas de la trayectoria P4 no son coloreadas con el color j aśı la única arista en
T1 que es coloreada con el color j es vk+(j+1)vk+(j+2), entonces la trayectoria T1 es una vjvl-
geodésica arcóıris.
Subcaso(2.e.iii).- l < k + (j + 1).
Sean T1 = (vj, γn, vl) y T2 = P4 ∪ (vk+(j+2), γ−1n , vl) las dos vjvl-trayectorias. Observemos
que l(T1) = l((vj, γn, vl) y como l < k + (j + 1), entonces l(T1) < (k + j + 1) − j = k + 1,
aśı l(T1) ≤ k, por otro lado l(T2) = l(P4) + l((vk+(j+2), γ−1n , vl)) ≥ (k − 1) + 2 = k + 1 ya
que l < k + (j + 1) aśı l((vk+(j+2), γ
−1
n , vl)) > (k + (j + 2)) − (k + (j + 1)) = 1 por lo que
l((vk+(j+2), γ
−1
n , vl)) ≥ 2. Aśı, l(T1) < l(T2) por lo que la trayectoria T1 es una vjvl-geodési-
ca. Ahora, como A(T1) ⊆ A(P3 \ {vk+(j+1), vk+(j+2)}) y como en la trayectoria P3 las únicas
aristas que repiten color son vjvj+1 y vk+(j+1)vk+(j+2), entonces T1 es una vjvl-geodésica arcóıris.
Por lo tanto, la coloración C1 es una (k + 1)-fuerte coloración arcóıris de las aristas de γn.
Por el teorema 2.2 se tiene que k =diám(γn) ≤ rc(γn) ≤ src(γn) ≤ k+1 entonces rc(γn) = k
ó rc(γn) = k + 1.
Afirmación.- rc(γn) = k + 1.
Supongamos que rc(γn) = k. Por lo tanto, existe C
′
una k-coloración arcóıris de las aristas de
γn. Sean u y v dos vértices en γn tales que diám(γn) = d(u, v). Supongamos sin pérdida de
generalidad que u aparece antes que v en γn.
Como el ciclo γn es impar, entonces para las uv-trayectorias T1 = (u, γn, v) y T2 = (u, γ
−1
n , v),
una debe de tener longitud k y la otra debe tener longitud k+1. Supongamos que la trayectoria
T1 tiene longitud k mientras que T2 tiene longitud k + 1. Aśı, T1 es una uv-geodésica arcóıris
mientras que T2 no es una trayectoria arcóıris ya que C
′
es una k-coloración.
42 CAPÍTULO 2. COLORACIÓN ARCOÍRIS EN GRÁFICAS
Ahora bien, como C
′
es una k-coloración arcóıris, supongamos sin pérdida de generalidad
que C
′
(vk+1vk+2) = k.
Consideremos los vértices v1,vk+1 y vk+2. Observemos que para los vértices v1 y vk+1 la tra-
yectoria Q1 = (v1, v2)∪(v2, γn, vk+1) es una geodésica ya que para la otra v1vk+1-trayectoria, por
ser γn un ciclo impar, debe tener longitud igual a k+1. Por lo tanto, Q1 es una geodésica arcóıris.
De forma análoga para los vértices v1 y vk+2 la trayectoria Q2 = (v1, vn)∪ (vn, γ−1n , vk+2) es
una geodésica arcóıris. Aśı Q1 y Q2 son geodésicas arcóıris de longitud k.
Como C
′
es una k-coloración arcóıris, implica que existe una arista en la geodésica Q1 y
otra en la geodésica Q2 tales que son coloreadas con el color k. Determinemos cuáles son las
aristas que repiten el color k. Ver figura 2.13.
Figura 2.13: La gráfica γn, rc(γn) = k ó rc(γn) = k + 1.
Consideremos a la trayectoria S1 = (v2, γn, vk+1) ∪ (vk+1, vk+2) y también a la trayectoria
S2 = (vn, γ
−1
n , vk+2) ∪ (vk+2, vk+1), donde l(S1) = k = l(S2). Como C
′
es una k-coloración ar-
cóıris y γn es un ciclo impar, entonces S1 y S2 son geodésicas arcóıris, ya que las otras posibles
trayectorias tienen longitud k + 1.
Como S1 = (v2, γn, vk+1)∪ (vk+1, vk+2) es una geodésica arcóıris y C
′
(vk+1vk+2) = k, implica
que en la trayectoria (v2, γn, vk+1) ninguna de sus aristas es coloreada con el color k. Por lo
tanto, para Q1 = (v1, v2)∪(v2, γn, vk+1) por ser una geodésica arcóıris se tiene que C
′
(v1v2) = k.
Por otra parte, como S2 = (vn, γ
−1
n , vk+2) ∪ (vk+2, vk+1) es una geodésica arcóıris y como
supusimos que C
′
(vk+1vk+2) = k, implica que para la trayectoria (vn, γ
−1
n , vk+2) ninguna de sus
aristas es coloreada con el color k. Por lo tanto, para Q2 = (v1, vn)∪ (vn, γ−1n , vk+2) por ser una
geodésica arcóıris se tiene que C
′
(v1vn) = k.
Aśı v1v2 ∈ A(Q1) y vnv1 ∈ A(Q2) son tales que C
′
(v1v2) = C
′
(vnv1) = k.
Por último, observemos que para los vértices v2 y vn no existe una v2vn-geodésica arcóıris.
Veamos la razon: sean T1 = (v2, v1, vn) y T2 = (v2, γn, vn) las dos v2vn-trayectorias y como
C
′
(v1v2) = C
′
(vnv1) = k, implica que T1 no es una v2vn-trayectoria arcóıris. Por otro lado,
l(T2) = l(γn)− l(T1) = (2k + 1)− 2 = 2k − 1, entonces l(T2) = 2k − 1 > k, lo que implica que
2.4. COLORACIÓN ARCOÍRIS PARA RUEDAS 43
el número de aristas es mayor a k y como rc(γn) = k, tenemos que al menos existen dos aristas
en la trayectoria T2 que repiten color. Aśı, T2 no es una v2vn-trayectoria arcóıris.
Por lo tanto, para los vértices v2 y vn del ciclo γn no existe una v2vn-trayectoria arcóıris
y esto contradice el hecho de que C
′
es una k-coloración arcóıris, entonces concluimos que
rc(γn) = src(γn) = k + 1.
2.4. Coloración arcóıris para ruedas
En esta sección construimos gráficas a partir de los ciclos, a estas gráficas se les conoce como
ruedas. Mostramos como determinar al mı́nimo entero k para el cual existe una k-coloración
arcóıris y también determinamos al mı́nimo entero k
′
para el cual existe una k
′
-fuerte coloración
arcóıris de una rueda.
Definición 2.10. Sea Wn una gráfica tal que V (Wn) = V (γn) ∪ {v}, donde v /∈ V (γn) y
A(Wn) = A(γn) ∪ {vu| u ∈ V (γn)}. A Wn se le llamará rueda de orden n+ 1.
A continuación encontraremos al mı́nimo entero k para el cual existe una k-coloración
arcóıris para este tipo de gráficas.
Proposición 2.3. Si Wn es una rueda con n ≥ 3, entonces el mı́nimo entero k para el cual
existe una k-coloración arcóıris de Wn, está determinado por:
rc(Wn) =

1 si n = 3
2 si 4 ≤ n ≤ 6.
3 si n ≥ 7.
Demostración. Supongamos que la ruedaWn consiste de un ciclo de longitud n, γn = (v1, v2, . . . ,
vn, vn+1 = v1) y otro vértice v unido a cada vértice de γn. Consideremos los siguientes casos
sobre n:
Caso 1.- n = 3.
Figura 2.14: W3.
Como la rueda W3 es isomorfa a la gráfica K4, es decir, es una gráfica completa y por la
proposición 2.1(a), sabemos que si G es una gráfica completa, entonces src(G) = 1 y por la
proposición 2.1(d), sabemos que si src(G) = 1, entonces rc(G) = 1.
Por lo tanto rc(K4) = 1, aśı rc(W3) = 1.
44 CAPÍTULO 2. COLORACIÓN ARCOÍRIS EN GRÁFICAS
Caso 2.- 4 ≤ n ≤ 6.
En este caso Wn no es completa. Por definición de rueda se tiene que diám(Wn) = 2 y por
el teorema 2.2 tenemos que 2 ≤ rc(Wn).
Definamos una