Résumé | Les configurations de Truemper que sont les pyramides, les theta-graphes, les prismes et les roues permettent de définir une famille de graphes les excluant en tant que sous-graphes induits : les "universally signable graphs". Je présenterais lors de ce GT des résultats de complexités sur la détection de ces sous-graphes, et plus précisemment celui sur la détection de la roue. |