Colorir gráficos planares

21

Considere o conjunto de gráficos planares em que todas as faces internas são triângulos. Se houver um ponto interno de grau ímpar, o gráfico não poderá ter três cores. Se todo ponto interior possui grau uniforme, ele sempre pode ser de três cores? Idealmente, eu gostaria de um pequeno contra-exemplo.

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

Respostas:

25

Sim, este é um corolário do Teorema das Três Cores, veja na parte inferior aqui: http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html

domotorp
fonte
11
Obrigado. Você tem uma referência para uma prova?
Lance Fortnow
3
Você pode olhar para estes dois documentos: google.com/… e google.com/…
Joseph Malkevitch
6
Para acrescentar às referências de Malkevitch: a equivalência de 3 cores e graus pares para triangulações planares é geralmente atribuída a PJ Heawood, "No teorema do mapa de quatro cores". Trimestral J. Pure Appl. Matemática. 29: 270–285, 1898. No entanto, os artigos que Malkevitch ligou têm mais a dizer sobre essa atribuição.
David Eppstein
6
Além disso, o corolário não é mencionado nas notas de Hull, apenas o teorema das três cores. Porém, a partir de um gráfico G com três conexões, com faces internas triangulares e até vértices internos, é possível formar um gráfico planar máximo 2G com vértices pares, simplesmente costurando duas cópias de G na face externa. Se G não estiver conectado em três cores, é possível colorir três componentes de três cores independentemente.
David Eppstein
24

S3

Gil Kalai
fonte