Graphes planaires
Problème
Caractérisation des graphes planaires
Propriétés
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:
Reconnaissance
Fraysseix–Rosenstiehl et DFS https://en.wikipedia.org/wiki/Left-right_planarity_test ; papier https://arxiv.org/pdf/math/0610935
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 :
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
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 ?
Algorithmes de coloration de listes
5 liste colorable.
Variantes
TBD pays non connexes TBD colonies lunaires
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
Odds and ends
TBD
- 3 coloriable et problème de la galerie d'art : https://fr.wikipedia.org/wiki/Problème_de_la_galerie_d'art
- isomorphisme de graphe planaire