Coloreabilidad de gráficos planos.

Question

Estoy tratando de mostrar que cada planar simple grafo sin ciclos de longitud {4,5,6,7,8,9,10,11} es 3-colourable.

Aquí es lo que he hecho hasta ahora.

Sea S el conjunto de todos los gráficos para que la afirmación es falsa.

Elija G de S con un mínimo de V(G)=n,de la que dicen es decir G es el mínimo contraejemplo.

Me mostró G no puede tener un vértice de grado en la mayoría de los 2 y que G no tiene un corte vértice.

A continuación, me dicen que si H es en S, entonces H tiene un corte vértice o un vértice de grado en la mayoría de los 2

Traté de mostrar este por el método de descarga por dar un suplemento de d(v)-6 a cada vértice y un cargo de 2|f|-6 a cada cara. Así que el total de carga que se le aplica a la gráfica es de -12

No estoy seguro de cómo proceder a partir de aquí, sin embargo.

Answer 1

Vamos a H en S Deje que c(f): Encargado de la cara f c(v): Encargado de la cara de v

Caso 1: H tiene un corte vértice. Entonces estamos hecho

Caso 2: H no tiene corte vértice

Dar un cargo de d(v)-6 a cada vértice y un cargo de 2|f|-6 a cada cara La carga Total=-12

Si es posible, H no tiene ningún vértice de grado en la mayoría de los 2

Como |f|>=3, por lo tanto, c(f)>=0 Por lo tanto, no existe un vértice v c(v)<0 es decir d(v)<6 También, d(v)>=3

Ahora, vamos a cada cara de longitud >=12 contribuir a un cargo de 3/2 a cada uno de sus vértices Como v no es un corte de vértice, por lo tanto es adyacente a d(v) caras diferentes También, si una cara es un triángulo, luego caras adyacentes no puede ser un triángulo(de lo contrario obtendríamos un 4-ciclo)

Por lo tanto, todas las otras caras de la longitud de al menos 12

Como d(v)>=3 ,es adyacente a al menos 2 caras de longitud de al menos 12 y de ahí se obtiene cargo adicional de al menos 3 Por lo tanto, c(v)>=0

Ahora, c(f)=2|f|-6-3/2|f|=|f|/2-6>=0 siempre que |f|>=12

Por lo tanto, todos los vértices y las caras ahora tienen carga positiva(contradice el hecho de que la carga total es de -12)

Así que H tiene un vértice de grado <=2

Así reclamar la tiene, por lo tanto G no puede ser en S(la contradicción como G es el mínimo contraejemplo)