Autour des graphes sans roues
Pierre Aboulker, LIAFA

Une roue est un graphe formé d'un cycle sans cordes et d'un sommet extérieur au cycle ayant au moins 3 voisins dans le cycle. Un propeller est un graphe formé d'un cycle sans cordes et d'un sommet extérieur au cycle ayant au moins 2 voisins dans le cycle. Tout l'exposé tournera autour des graphes sans roues i.e. des graphes ne contenant pas de roues en tant que sous-graphes induits.
Je montrerais d'abord comment, en utilisant Lex-BFS, on peut trouver en temps linéaire la plus grosse clique d'un graphe sans roues. J'indiquerais aussi comment, avec la même méthode, on peut améliorer les algorithmes existant pour trouver la plus grosses cliques dans les graphes sans trous pairs ainsi que dans les graphes sans "square-3-PC(.,.)".
Ensuite, je présenterais un théorème de structure sur les graphes sans propellers (notez que la classe des graphes sans propellers est une sous-classe de la classe des graphes sans roues) qui permet de détecter les propellers en temps polynomial ainsi que de colorer et d'arrête-colorer les graphes sans propellers en temps polynomial.