Colorear Gráficos Planos

21

Considere el conjunto de gráficos planos donde todas las caras internas son triángulos. Si hay un punto interior de grado impar, el gráfico no puede ser de tres colores. Si cada punto interior tiene un grado par, ¿puede ser siempre de tres colores? Idealmente, me gustaría un pequeño contraejemplo.

graph-theory co.combinatorics graph-colouring Lance Fortnow
fuente

Respuestas:

25

Sí, este es un corolario del Teorema de los tres colores, ver al final aquí: http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html

domotorp
fuente
1
Gracias. ¿Tiene una referencia para una prueba?
Lance Fortnow
3
Puede consultar estos dos documentos: google.com/… y google.com/…
Joseph Malkevitch el
66
Para agregar a las referencias de Malkevitch: la equivalencia de 3-colorabilidad e incluso grado para triangulaciones planas generalmente se atribuye a PJ Heawood, "En el teorema del mapa de cuatro colores". Trimestralmente J. Pure Appl. Mates. 29: 270–285, 1898. Sin embargo, los documentos vinculados por Malkevitch tienen más que decir sobre esta atribución.
David Eppstein
66
Además, el corolario no se menciona en las notas de Hull, solo el teorema de 3 colores en sí. Pero a partir de un gráfico G conectado a 3 con caras internas triangulares e incluso vértices internos, se puede formar un gráfico plano máximo 2G con vértices uniformes simplemente cosiendo dos copias de G en la cara externa. Si G no está conectado a 3, uno puede colorear 3 de sus componentes conectados de forma independiente.
David Eppstein