Résumé: Le nombre de graphes planaires à n sommets (non-isomorphes, non étiquetés) est de l’ordre de c(n+o(n)), où c=O(1). Quel est le plus petit graphe qui les contient tous comme sous-graphes induits ? Nous montrons ici qu’il suffit de n(1+o(1)) sommets. Ce résultat, de toute évidence optimal asymptotiquement, repose sur des avancées majeures en théorie structurelle des graphes, dont nous discuterons également.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne