Coloration :
graphes parfaits,
hypergraphes bicritiques,
coloration par listes
[ Français | English ]
Coloration :
graphes parfaits,
hypergraphes bicritiques,
coloration par listes
Connexité :
coupe min,
coupe max,
"cutwidth"
Absorption :
ensembles dominants,
noyaux
Les graphes parfaits ont été définis par Claude Berge en 1960. Ces graphes généralisent un certain nombre de familles classiques de graphes (triangulés, transitivement orientables, line-graphes de bipartis, etc) ayant de "belles propriétés" de coloration. Berge a conjecturé qu'un graphe est parfait si et seulement si lui-même et son complémentaire ne contiennent comme sous-graphe induit aucun cycle de longueur impaire au moins cinq sans corde.
Cette "Conjecture Forte des Graphes Parfaits" n'est pas résolue à ce jour, mais elle a suscité un corpus important de recherche. De plus, les graphes parfaits forment une des rares classes de graphes pour lesquels on sait résoudre le problème de la coloration en temps polynomial, du moins en théorie (algorithme de Grötschel, Lovász et Schrijver, basé sur la méthode de l'ellipsoïde); en pratique les auteurs s'attachent à trouver des algorithmes combinatoires aussi simples et efficaces que possible.
Nous nous intéressons à résoudre la Conjecture
Forte des Graphes Parfaits pour de nouvelles classes, ainsi
qu'à trouver des algorithmes de coloration pour les graphes
parfaits, ces deux questions étant en fait intimement
mêlées. Plusieurs d'entre nous ont
particulièrement exploré les classes des graphes
parfaitement ordonnables, des graphes parfaitement contractiles, et
des graphes de quasi-parité. Voir la liste de publications de
Myriam Preissmann, de Frédéric
Maffray, ou la thèse de Cláudia Linhares Sales.
Les hypergraphes bicritiques pour le nombre chromatique peuvent curieusement être rattachés à la synthèse des portes logiques (logique monotone) au moyen d'autres portes. Le long projet d'article de Claude Benzaken From Logical Gates Synthesis until Bicritical Clutters en explique l'origine.
Disons pour être court qu'un hypergraphe bicritique est un hypergraphe tel que, pour chaque arête e, l'hypergraphe formé des arêtes ne rencontrant pas e voit son nombre chromatique diminuer de deux. Les hypergraphes bicritiques qui sont des graphes sont l'objet d'une conjecture (1968) non encore résolue de Lovász (ce seraient les graphes complets !).
Les hypergraphes bicritiques pour les nombres chromatiques 2 et 3 sont parfaitement connus (pour 3 ce sont les hypergraphes ipso-transversaux sans sommets isolés et avec plus d'une arête); on soupconne que, pour toute valeur du nombre chromatique, beaucoup des nombreuses propriétés des ipso-transversaux sont conservées. Compte tenu d'une validation possible de la conjecture de Lovász citée plus haut, les hypergaphes bicritiques pourraient jouer pour les hypergraphes le rôle que jouent les cliques pour les graphes, et permettre par exemple de définir le concept d'hypergraphe parfait.
Un hypergraphe ipso-transversal nommé l'aile volante :
Etant donné la difficulté de manipulation d'hypergraphes, le logiciel Clutter a été dédié à ce thème.
Un graphe G d'ordre n est k-liste colorable si, quelle que soit la donnée de n listes de taille k (une par sommet), il est possible d'attribuer à chaque sommet une couleur de sa liste, de sorte que deux sommets voisins quelconques aient des couleurs différentes. Ce concept généralise la coloration ordinaire. De manière analogue, on peut définir le nombre chromatique de liste noté ChiL(G) qui est clairement supérieur ou égal à Chi(G). En fait, parmi les graphes bipartis ChiL peut avoir une valeur arbitrairement grande.
L'analogue d'un théorème de Hajós montre le rôle prépondérant des bipartis complets, pour lesquels il est cependant NP-dur de déterminer la valeur de ChiL.
Une deuxième voie de recherche est de caractériser les graphes pour lesquels les deux paramètres de coloration sont égaux : en particulier, la conjecture toujours ouverte de Vizing (qui est un des premiers, avec Erdös, Rubin et Taylor, à avoir introduit ce concept) qui affirme l'égalité de ChiL et de Chi pour les line-graphes. Voir la thèse de Sylvain Gravier.
Une coupe d'un graphe d'ordre n est une bipartition des sommets, considérée comme l'ensembles des arêtes qui vont d'une partie à l'autre. Etant donné un poids positif sur chaque arête, trouver une coupe de poids minimum est un problème classique et bien résolu. On peut aussi chercher toutes les coupes de taille minimum; ceci est possible et conduit à une représentation du graphe par un certain "cactus" (graphe dont les blocs sont des cycles), et donne une borne quadratique en n sur le nombre total de coupes minimum. Nous avons étudié les graphes ayant le plus grand nombre possible de coupes minimum (voir l'article de Lehel, Maffray et Preissmann, ref. 24 ici).
Le problème de la cutwidth (trouver un ordre linéaire des sommets qui minimise la taille maximum des coupes ordonnées) trouve des applications importantes en conception de circuits intégrés (VLSI), mais il est aussi NP-complet. Ce problème devient polynomial pour les arbres, et nous avons un algorithme pour des arbres "réguliers" (voir la référence 23 dans les publications de Myriam Preissmann).
Un ensemble dominant est un ensemble de sommets A tel que tout sommet hors de A a un voisin dans A. Trouver un ensemble dominant de taille minimale est un problème très difficile ("NP-complet"). Nous cherchons à résoudre ce problème dans le cas de graphes particuliers de type grille (produit carré, ou croisé, de deux chaînes).
Un noyau dans un graphe orienté est un ensemble N de sommets deux à deux non-adjacents tel que tout sommet hors de N a un successeur dans N. L'existence d'un noyau est souvent obtenue en imposant des conditions sur les circuits impairs. Il existe certains liens entre les graphes parfaits et la théorie des noyaux, formulés par une conjecture de Berge et Duchet (voir par exemple les références [1, 2, 11, 16, 20] dans les publications de Frédéric Maffray). Une partie de cette conjecture a été démontrée récemment par Endre Boros et Vladimir Gurvich, et met en évidence une connection étroite avec des résultats classiques de la théorie des jeux.
Retour à la page de l'équipe