Si G es un grafo tal que $\Delta(G) = 3$ y $\chi'(G) \le 4$

Question

$\chi'(G)$ la cromática índice de $G$, $\chi(G)$ su cromática número y $\Delta(G)$ su grado máximo.

Aquí está la solución que me dan, pero no entiendo esto:

Aplicar Brooks' el teorema de la gráfica de línea de G.

Veo cómo $\chi'(G) = \chi(L(G))$.

Pero un grafo G con $\Delta(G) = 3$, evidentemente, puede tener un gráfico de línea tal que $\Delta(L(G)) > 3$, tomemos, por ejemplo:

Además, el gráfico de línea que podría llegar a ser un extraño ciclo de...

Alguna idea de a dónde ir a partir de ahí?

Answer 1

Usted no necesita preocuparse acerca de los ciclos impares, ya que pueden ser de color con tres colores y se le permite cuatro.

Es necesario justificar tres cosas:

1. Muestran que el máximo grado posible es $4$ (no es tan malo, creo).
2. Demuestra que tu gráfica no puede ser el grafo completo en cinco vértices, es decir, que usted no va a obtener una camarilla (usted puede comprobar yendo hacia atrás, si te gusta).
3. No importa si usted recibe un extraño ciclo.

La puede utilizar Arroyo del teorema en todo su esplendor.

Para más información, este resultado es llamado Vizing del Teorema.

Answer 2

Supongamos $\Delta(G) = 3$. Tenemos que mostrar que 4 colores suficientes para el color de los bordes de la gráfica.

Deje $uv$ ser una ventaja en $G$. La cantidad de bordes que comparten un punto final común con esta ventaja? Desde $\Delta=3$, en la mayoría de los otros dos bordes, además de a $uv$ es el incidente con el vértice $u$, y del mismo modo para $v$. Así, en la mayoría de las $2+2=4$ bordes comparten un endvertex con edge $uv$. Así, en el gráfico de línea de $G$, el vértice $uv$ tiene el grado máximo de 4. Si esta línea gráfica de $L(G)$ no es un extraño ciclo o un grafo completo, por el Arroyo del teorema de sus vértices (y, por tanto, los bordes de $G$) puede ser de 4 colores.

Si el gráfico de líneas es un extraño ciclo, sus vértices pueden ser de 2 o 3 colores, por lo tanto 4 colores es suficiente. Si el gráfico de líneas es el grafo completo $K_r$, entonces se debe considerar el valor de $r$. Si $r=3$, $K_3$ es la línea gráfica de $K_3$ o una estrella de $K_{1,3}$, y en el caso de 3 colores es suficiente. Si $r \ge 4$, entonces esto $K_r$ surgió a raíz de una $G$ que es necesariamente una estrella $K_{1,r}$. (Este es un resultado básico en gráficos de líneas: cualquier camarilla en el $L(G)$ con 4 o más vértices es inducida por una estrella en $G$.) Desde $\Delta(G) =3$, esta estrella tiene exactamente 3 aristas; por lo tanto $r=3$ y tres colores basta de nuevo.

En otras palabras, no hay un clique de tamaño 4 o más en la línea del gráfico de $L(G)$ si $\Delta(G)=3$. En general, a todas las camarillas en $L(G)$ surgir de cualquiera de las estrellas de la $K_{1,r}$ $G$ (es decir, el conjunto de los bordes de las $G$ que comparten un endvertex) o triángulos en $G$.