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.