MASCOTTE no longer exists => visit the new COATI project-team
 


Seminaire MASCOTTE
Coloration des graphes presque planaires

par Frédéric Havet


Date :16/02/10
Time :10:30
Location :Kahn 2 et 3


Le célèbre Théorème des Quatre Couleurs affirme que tout graphe planaire admet une coloration en quatre couleurs. Dans cet exposé, nous nous intéresserons aux graphes qui ne sont pas planaires mais presque, c'est à dire qui ont un petit nombre de croisements ou qui peuvent etre rendus planaires en retirant un petit nombre d'aretes.
En particulier, nous montrerons que si un graphe peut etre rendu planaire en otant au plus 3 aretes alors il est 5-colorable. Nous montrerons également que tout graphe de nombre de croisements au plus 4 est 5-colorable sauf s'il contient une clique à six sommets.
Enfin nous regarderons des problèmes voisins notamment la coloration par listes des graphes presque planaires.


Page des séminaires