grafos



Coloración De Grafos Y Polinomios Cromáticos
DEFINICIÓN 11.22
Si G= (V, E) es un Grafo no dirigido, una coloración propia de G, ocurre cuando coloreamos los vértices de G de modo que si {a,b} es una arista en G entonces a y b tienen diferentes colores. (Por lo tanto, los vértices adyacentes tienen colores diferentes). El número mínimo de colores necesarios para una coloración propiade G es el número cromático de G y se escribe como Х (G).
EJERCICIO 11.28
Para el grafo G de la figura 11.83, partimos del vértice a y junto a cada vértice escribimos el numero de un color necesario parauna coloración propia de los vértices de G considerando hasta ese punto. Al parecer al vértice b, el 2 indica que necesitamos un segundo color.







Puesto que los vértices a y b sonadyacentes. Seguimos en orden alfabético hasta f y vemos que es necesario 2 colores para una coloración propia de {a, b, c, d, e, f}. Para el vértice g, necesitaremos un tercer color, el cual también puedeusarse para el vértice h, puesto que {g, h} no es una arista de G. así, este método de etiquetado de una coloración secuencial nos proporciona una coloración propia de G, por lo que X (G) 3. Como k3es un subgrafo de G [por ejemplo, el subgrafo inducido por a, b, g es (isomorfo a) k3], tenemos que X (G)3, por lo que X (G)=3.




EJEMPLO 11.30
Sea G el grafo que se muestra en la figura11.84. Para U= {b, f, h, i], el subgrafo inducido de G es isomorfo a k4, por lo que X (G)X (k4)=4. Por lo tanto si podemos determinar una coloración propia de los vértices de G con 4 colores entoncessabremos que X (G)=4. Una forma de lograrlo es colorear los vértices e, f, g en azul; los vértices b, j en rojo, los vértices c, h en blanco y los vértices a, d, i en verde.





Sea G un grafo nodirigido y sea λ el numero de colores disponibles para la coloración propia de los vértices de G. nuestro objetivo es encontrar una función polinomial P (G, λ), en la variable λ llamada polinomio...