Coloration des graphiques planaires

21

Considérons l'ensemble des graphes planaires où toutes les faces internes sont des triangles. S'il y a un point intérieur de degré impair, le graphique ne peut pas être tricolore. Si chaque point intérieur a un degré égal, peut-il toujours être tricolore? Idéalement, je voudrais un petit contre-exemple.

graph-theory co.combinatorics graph-colouring Lance Fortnow
la source

Réponses:

25

Oui, c'est un corollaire du théorème des trois couleurs, voir en bas ici: http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html

domotorp
la source
1
Merci. Avez-vous une référence pour une preuve?
Lance Fortnow
3
Vous pouvez consulter ces deux articles: google.com/… et google.com/…
Joseph Malkevitch
6
Pour ajouter aux références de Malkevitch: l'équivalence de la 3-colorabilité et même du degré pour les triangulations planes est généralement attribuée à PJ Heawood, "Sur le théorème de la carte à quatre couleurs". Trimestriel J. Pure Appl. Math. 29: 270-285, 1898. Cependant, les articles liés par Malkevitch ont plus à dire sur cette attribution.
David Eppstein
6
De plus, le corollaire n'est pas mentionné dans les notes de Hull, seulement le théorème des 3 couleurs lui-même. Mais à partir d'un graphe G à 3 connexions avec des faces internes triangulaires et même des sommets internes, on peut former un graphe planaire maximal 2G avec des sommets pairs simplement en cousant deux copies de G sur la face externe. Si G n'est pas connecté en 3, on peut colorier indépendamment ses composants connectés en 3.
David Eppstein
24

S3

Gil Kalai
la source