Sujet : Constructions logiques pour des classes de graphes

Responsable : Bruno Courcelle
Téléphone : 05 40 00 60 86
e-mail : courcell@labri.fr
Site Web : http://www.labri.fr/~courcell/ActSci.html
Equipe : LAAA

Présentation du sujet :

Les propriétés des graphes telles que l'existence, soit de "bons coloriages" qui définissent des orientations, soit  de sous graphes particuliers (cf la caractérisation de Kuratowsky des graphes planaires), soit de relations d'ordres canoniques, sont essentielles pour construire des formules de la logique du second-ordre monadique qui définissent telle propriété ou telle transformation de graphes. Un vaste corpus de connaissances sur la structure de familles classiques de graphes reste à explorer dans une perspective d'application à ces constructions logiques.
Ces constructions logiques sont motivées par plusieurs questions ouvertes, dont une conjecture de D. Seese selon laquelle tout ensemble de graphes sur lequel la logique du second-ordre monadique  est l'image d'un ensemble d'arbres par une transformation définissable dans cette logique.
Cette conjecture semble très difficile à prouver ou à infirmer, mais plusieurs cas particuliers en ont été établis, en s'appuyant sur des propriétés fines de classes particulières de graphes : graphes d'intervalles, graphes de comparabilité, ordres série-parallèle.
D'autre questions méritent un examen approfondi : sur quels graphes peut-on définir un ordre total en logique du second-ordre monadique ? Dans le cas d'un graphe infini dénombrable, il y a lieu de distinguer les ordres totaux possibles selon leurs types N, Z, Q, autre ?

Le sujet consiste à étudier ces questions et les questions connexes à partir de la vaste littérature existante sur les structures des classes de graphes.


Mot-clés : Graphes, structuration des graphes, planarité, logique du second-ordre monadique, configurations interdites, ensembles ordonnés.
Références :
Articles fournis sur demande par B. Courcelle.

Mise à jour :  Février 2004.