Théorème de Robertson-Seymour

Carte Commune · n° 489797

En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour affirme qu'un certain classement partiel entre graphes non orientés possède des propriétés remarquables (c'est un bel ordre). Ce théorème a pour conséquence qu'il devient possible de caractériser de nombreuses familles de graphes par une liste finie de graphes qu’elles ne contiennent pas. Ce théorème généralise ainsi le théorème de Kuratowski, qui caractérise les graphes planaires comme ceux ne contenant pas deux graphes particuliers. Le théorème de Robertson–Seymour est également appelé le théorème des mineurs, car le classement partiel évoqué dans son énoncé est défini par la relation « être un mineur ». Le théorème équivaut ainsi à dire que toute famille F de graphes fermée, c'est-à-dire telle que les mineurs des graphes de F appartiennent aussi à F, peut être caractérisée par un ensemble fini de « mineurs exclus ». Connu, avant qu'il soit démontré, sous le nom de conjecture de Wagner, ce théorème...

Lire sur Wikipédia