Ionona Ranaivoson (GREYC, Université de Caen)

Idée directrice : certains problèmes sur un graphe pourraient être facilités par la connaissance de relations d’adjacence entre des cycles de ce graphe. Mais, le nombre de cycle d’un graphe \(G\) étant, en général, exponentiel par rapport à sa taille, nous allons plutôt étudier des relations d’adjacence entre les éléments de bases particulières de cycles de \(G\), dont les éléments sont des trous (ou cycles sans cordes), appelées couvertures par trous de \(G\).

Dans un premier temps, nous définissons, pour tout graphe non orienté \(G\), ce qu’est “une couverture par trous”. Puis nous associons à chaque couverture \(C\) par trous de \(G\) un graphe particulier, appelé « graphe réduit d’adjacence des trous », dont les sommets sont des trous et des chemins de \(G\), décrivant les adjacences entre les éléments de \(C\).

Comme application, nous donnerons une nouvelle caractérisation des SP-graphes (graphes série-parallèles) et sous-classes (graphes extra-planaires) à l’aide de graphes réduits d’adjacence de trous. Puis, à l’aide de cette caractérisation, nous revisiterons des problèmes de SP-graphes, dont :

  • une coloration gloutonne (le choix de la couleur d’un sommet est pris localement) et optimale de SP-graphes (avec 2 couleurs si 2-colorable et avec 3 couleurs sinon);
  • la reconnaissance de SP-graphes et de ses sous-classes;
  • l’isomorphisme de graphes et l’isomorphisme de sous-graphes pour les graphes extra-planaires, etc.