Chudnovsky Maria

En 2002, Maria Chudnovsky a contribué à résoudre une question qui reliait deux façons de regarder un graphe : le nombre de couleurs nécessaires pour colorier ses sommets, et la taille de son plus grand groupe de sommets tous reliés entre eux. Un graphe parfait est une structure où ces deux nombres coïncident, non seulement pour le graphe entier, mais aussi pour chacun de ses sous-graphes induits. Cette propriété permet de savoir quand une coloration utilise réellement le minimum de couleurs. Elle éclaire notamment l'organisation de canaux dans un réseau de communication.

Un graphe est une collection de sommets reliés par des arêtes. Le nombre chromatique d'un graphe, noté χ(G), est le plus petit nombre de couleurs permettant de colorier ses sommets de sorte que deux sommets reliés par une arête aient des couleurs différentes. Le nombre clique, noté ω(G), est le nombre maximal de sommets deux à deux reliés par une arête. Un graphe est parfait lorsque, pour tout sous-graphe induit H obtenu en conservant un ensemble quelconque de sommets et toutes les arêtes entre eux, on a $\chi (H)=\omega (H)\backslash chi(H)=\backslash omega(H)$.

La conjecture forte des graphes parfaits donne un critère équivalent : un graphe est parfait si et seulement si le graphe lui-même et son complémentaire ne contiennent aucun cycle induit de longueur impaire au moins égale à cinq. Le complémentaire conserve les sommets et inverse la présence des arêtes entre sommets distincts. Le critère porte sur les cycles induits : des arêtes supplémentaires entre les sommets du cycle changeraient le sous-graphe considéré. Maria Chudnovsky, Neil Robertson, Paul Seymour et Robin Thomas ont démontré cette conjecture en 2002.

Considérons le cycle C₅, formé de cinq sommets v₁, v₂, v₃, v₄ et v₅, chaque sommet étant relié aux deux suivants dans le cycle. Les données sont les suivantes : il n'y a pas de triangle, le plus grand groupe de sommets tous reliés a donc 2 sommets, et le cycle est impair.

Pour le colorier, deux couleurs ne suffisent pas : en alternant les couleurs le long de quatre arêtes, la cinquième arête relie deux sommets qui recevraient la même couleur. Trois couleurs suffisent, par exemple en donnant une couleur à v₁ et v₃, une autre à v₂ et v₄, et une troisième à v₅. On obtient donc χ(C₅) = 3, tandis que ω(C₅) = 2.

Comme ces deux nombres diffèrent, C₅ n'est pas parfait. Son complémentaire est encore un cycle à cinq sommets. Il contient donc lui aussi un cycle impair induit de longueur 5 : cet exemple vérifie concrètement la nécessité du critère de la conjecture forte des graphes parfaits.

Dans un réseau de communication, on peut représenter par un sommet chaque liaison ou chaque tâche qui doit recevoir un canal. Une arête relie deux éléments qui ne peuvent pas utiliser le même canal. Colorier les sommets revient alors à attribuer des canaux sans conflit.

Pour un graphe parfait, le nombre minimal de canaux est égal à la taille du plus grand ensemble d'éléments mutuellement incompatibles. Le résultat sur les graphes parfaits permet donc d'identifier une situation où une borne évidente devient exactement atteignable, au lieu de rester une simple estimation.

Un graphe biparti n'est pas synonyme de graphe parfait. Dans un graphe biparti, les sommets se répartissent en deux ensembles sans arête à l'intérieur d'un même ensemble ; cette propriété entraîne la perfection, mais un graphe parfait peut ne pas être biparti. Le cycle à quatre sommets en est un exemple parfait et biparti, tandis qu'un graphe complet à trois sommets est parfait sans être biparti.

Il ne faut pas non plus confondre le nombre clique avec le nombre chromatique. Le premier mesure un groupe de sommets tous adjacents ; le second mesure le nombre de couleurs nécessaire pour éviter les conflits. La perfection est précisément l'égalité de ces nombres pour tous les sous-graphes induits, et non leur égalité accidentelle pour le seul graphe de départ.

Le critère de la conjecture forte ne porte pas sur n'importe quel cycle impair. Il recherche un cycle induit de longueur au moins 5, c'est-à-dire sans arête supplémentaire entre deux sommets du cycle et avec 5 sommets ou davantage. Un triangle est impair, mais il ne constitue pas un obstacle au sens de ce critère.

La condition doit être vérifiée pour le graphe et pour son complémentaire. Examiner seulement le graphe peut laisser échapper un cycle impair induit dans le complémentaire. Dans l'exemple de C₅, les deux côtés du critère sont présents : le cycle lui-même et son complémentaire contiennent chacun un cycle induit de longueur 5.

Enfin, l'égalité χ(G) = ω(G) pour un seul graphe ne suffit pas à conclure qu'il est parfait. La définition exige cette égalité pour chaque sous-graphe induit. Le contrôle doit donc inclure les sous-structures obtenues en retirant des sommets, et pas seulement la structure initiale.

Le théorème fort des graphes parfaits transforme une propriété définie par des colorations en un critère structurel : l'absence de certains cycles impairs dans un graphe et son complémentaire. Cette passerelle entre optimisation et structure est l'un des prolongements conceptuels majeurs du travail de Maria Chudnovsky. Elle explique pourquoi un résultat issu de la théorie des graphes peut intervenir dans la recherche du nombre minimal de canaux d'un réseau.