 |
| Grafo de Catlin, tomado del libro Graph Theory de Bondy y Murty |
La composicion de un grafo B en un grafo A, representada por A[B] simplemente lo siguiente, cada vertice del grafo A ahora ya no es un vertice sino que ahora va ser un nuevo grafo!, en este caso una instancia del grafo B, y las aristas? pues lo logico seria, que si queremos unir dos grafos, unamos cada vertice de un grafo con cada vertice del otro.
Listo, entonces observen bien el grafo de alla arriba, es nada menos que un circuito de 5 vertices en el que cada vertice ha sido reemplazado por un grafo completo de tres vertices(osea, un triangulo), su nomenclatura
es $C_5[K_3]$.
Se le dice grafo de Catlin, por que Catlin lo utilizo para encontrar contraejemplos en la Conjetura de Hadwiger
Ahora este grafo puede ser generalizado a un $C_n[K_r]$, donde $C_n$ es un circuito de tamanho $n$ y $K_r$ es un grafo completo con $r$ vértices.
La pregunta de rigor es, cual es el menor numero de colores con que se puede pintar los vertices de este grafo tal que dos vertices del mismo color no son adjacentes.A este numero minimo se le llama numero cromatico del grafo.
Tal vez la pregunta es muy general en realidad no se como resolverla para cualquier n, r. Entonces vamos a partirla en varias subpreguntas.
Cual es el numero cromatico de un $C_5[K_3]$
Cual es el numero cromatico de un $C_5[K_r]$
Cual es el numero cromatico de un $C_n[K_3]$
y la mas general, Cual es el numero cromatico de un $C_n[K_r]$?
Bueno ahora si voy a necesitar ayuda asi que si alguien sabe la respuesta de la ultima pregunta me avisa jajaja.
Solucion para un C_5[K_3]:
ResponderSuprimirLo mas inocente seria pintar cada vértice de un color diferente, en este caso tenemos 15 colores usados para llenar todo el grafo. Claramente esta coloracion no es la mas eficiente.
Lo segundo mas inocente(y que yo hice) es hacer lo siguiente: Pintamos el primer K_3 usando tres colores, el segundo K_3 usando otros tres colores y el tercer K_3 usando otros tres colores, hasta ahi tenemos 9 colores, para pintar el cuarto y quinto K_3 simplemente repetimos los colores usados anteriormente, osea el cuarto K_3 lo pintamos exactamente igual al primer K_3 y el quinto K_3 lo pintamos exactamente igual al segundo K_3. Osea algo asi: (123)(456)(789)(123)(456)
Parece hasta ahi que nueve colores es una muy buena solucion, pero como sabemos que no lo podemos pintar con ocho??
Y la verdad es que sí podemos...de la siguiente manera (123)(456)(781)(234)(567).
Bueno primero con 9, ...ahora con 8, como sabemos que no podemos con 7? Una forma es probar todas las combinaciones con 7 colores y sabremos que no se puede, PERO, hay una manera mas inteligente de saber que NO es posible pintarlo con menos de 8 colores.
Supongamos existen 7 colores para pintar el grafo. Tenemos que el conjunto de vertices puede ser particionado en 7 partes {x1,x2,x3,x4,x5,x6,x7} tal que dos vertices que pertenecen a algun xi no pueden tener aristas en comun( a esto se le llama tambien conjunto estable o independiete ). Ahora fijense que para cubrir todos los vertices con estos 7 conjuntos, necesitamos POR LO MENOS que alguno tenga tres elementos (ya que tenemos que cubrir 15 vertices)
Pero valgan verdades esto es imposible, ya que no hay tres vertices en el grafo que no tengan ninguna arista entre ellos. Notamos que solo es posible encontrar 2 vertices que no tienen arista entre ellos.Por que?
Eliga un vertice cualquiera del primer K_3(por la simetria) y ahora note que cualquier otro vertice esta o bien en el cuarto o bien en el quinto K_3 mas no en los dos. Siendo asi, tenemos que cualquier xi tiene a lo mas dos elementos y por tanto necesito de por lo menos ocho colores para pintar todo el grafo.
Mas adelante las demas respuestas..
Para un C_5[K_n].
ResponderSuprimirEs una generalizacion del problema anterior, como es un C_5, entonces el tamanho de un conjunto estable máximo es también 2. Ahora, sea {x1,...,x_p} la coloracion del grafo, tenemos que 2p>= 5n y por tanto, p >= 5n/2. Pero no podemos afirmar a ciencia cierta que p =5n/2. Pare empezar puede ser decimal. Si no es decimal podemos tomar el entero superior, pero como sabemos que existe una tal coloracion de ese tamanho. Hay que mostrarla, y la coloracion es de la siguiente manera:
(123...n)(n+1...2n)(1,...,n/2,3n/2,...,2n)(n/2+1,...,n,n+1,(3n/2)-1)(n+1...2n).
Lo anterior suponiendo que n es par, para n impar se puede generalizar tomando el techo de 5n/2.