Graphes planaires

Problème

Caractérisation des graphes planaires

Propriétés

Coloration de graphes planaires

Théorème des 4 couleurs

TBD 6 par notre algo de coloration TBD 5 couleur : démonstration de Kempe.

Elle ne fonctionne pas pour 4 couleurs. Pourquoi ? TBD Une démo (fausse) du théorème des 4 couleurs par Kempe : https://www.youtube.com/watch?v=adZZv4eEPs8

TBD théorème des 4 couleurs :

• https://www.lix.polytechnique.fr/~werner/PI-4C/sujet4C.html
• 4 couleurs : https://inria.hal.science/hal-04034866/document

Colorable est NP-complet

TBD pareil que colorier les faces.

TBD 3 colorable planaire np-complet : https://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/chapter23.pdf ds 26

TBD on en déduit que trouver les 4 couleurs aussi. Sinon on fait comme 3-col et le graphe est 4-plan-col avec le gadget. ce qui donne les 3 couleurs également.

Algorithmes de coloration

• 6 coloration avec l'algo de coloration
• 5 coloration linéaire https://www.enseignement.polytechnique.fr/profs/informatique/Francois.Morain/INF431/X06/5col.pdf
• 4 coloration d'un graphe planaire 3 colorable (Kawarabayashi et Ozeki 2009) https://tgt.ynu.ac.jp/ozeki/2009KO2.pdf. Soit il sort une 4 coloration, soit il dit que le graphe n'est pas 3 colorable. Pourquoi n'est-ce pas en contradiction avec le fait que le problème est NP-complet ?

Applications

Dans des problèmes

3 colorable et problème de la galerie d'art : https://fr.wikipedia.org/wiki/Problème_de_la_galerie_d'art

Coloration de cartes de géographie

coloration de cartes de géographie (pourquoi souvent 6 couleurs ?)

Colorabilité et partage de secrets

TBD un sujet qui lie tout ce qu'on a fait jusqu'à maintenant.

https://fr.wikipedia.org/wiki/Preuve_à_divulgation_nulle_de_connaissance

Curry-Howard correspondance

Algorithmes de coloration de listes

5 liste colorable.

Variantes

TBD pays non connexes TBD colonies lunaires

Algorithmes

Dessin

TBD dessin avec 2-connexe https://perso.ens-lyon.fr/eric.thierry/Graphes2010/lucie-martinet.pdf

TBD dessin sans courbure dans un triangle:

• exemple https://ics.uci.edu/~eppstein/gina/schnyder/ ou https://ics.uci.edu/~eppstein/163/lecture10c.pdf
• papier https://acm.math.spbu.ru/~sk1/courses/1617f_au3/papers/schnyder-grid-embedding.pdf

Reconnaissance

Fraysseix–Rosenstiehl et DFS https://en.wikipedia.org/wiki/Left-right_planarity_test ; papier https://arxiv.org/pdf/math/0610935

• isomorphisme de graphe planaire

Références

-->