Théorème de Robertson-Seymour

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, démontré en 2004 par Neil Robertson et Paul Seymour, est considéré généralement comme un des résultats les plus importants de la théorie des graphes. Il a une démonstration extrêmement complexe et délicate, dont la publication, comportant plus de cinq cents pages, s'étale de 1983 à 2004 dans vingt articles de la revue Journal of Combinatorial Theory.

Le théorème n'est pas constructif (on ne connait d'ailleurs les listes explicites de mineurs exclus que dans très peu de cas), mais Robertson et Seymour ont montré qu'il a d'importantes conséquences en théorie de la complexité, car il garantit l'existence d'algorithmes rapides pour de nombreux problèmes de décision.

Présentation informelle du théorème

Un célèbre exemple historique : la modélisation par Euler du problème des ponts de Königsberg.
→

→

La théorie des graphes est la discipline mathématique (et informatique) qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des points. Ces modèles sont constitués par la donnée de « points », appelés des sommets (en référence aux polyèdres), et de « liens » entre ces points ; ces liens, pour les graphes étudiés ici, sont symétriques (les graphes sont dits non orientés) et sont appelés des arêtes.

Un graphe ne peut pas toujours être dessiné sur une feuille de papier (ou, plus rigoureusement, dans un plan) sans que les arêtes se coupent ; quand c'est possible, le graphe est alors dit planaire. Ainsi, l'explication de l'impossibilité de l'énigme des trois maisons est que le graphe qui modélise l'énigme n'est pas planaire. En 1930, Kuratowski a obtenu une caractérisation de tous les graphes planaires, légèrement reformulée quelques années plus tard par Wagner, sous la forme d'une liste de deux graphes ne devant pas être « contenus » dans un graphe donné pour que ce dernier soit planaire.

Ce graphe à 14 sommets et 21 arêtes ne peut être tracé sur une feuille de papier sans que ses arêtes se coupent (il n'est pas planaire), mais peut être ainsi tracé sur un tore (un pneu) : on dit que c'est un graphe toroïdal.

• Les deux mineurs exclus des graphes planaires.
• 
  Le graphe complet $K_{5}$, ayant 5 sommets et 10 arêtes.
• 
  Le graphe biparti complet $K_{3,3}$, ayant 6 sommets et 9 arêtes.

Pour de nombreuses familles de graphes, par exemple ceux pouvant être dessinés sur la surface d'un pneu (en mathématiques, on parle de tore, et les graphes ainsi traçables sont les graphes toroïdaux), on peut se demander s'il existe une caractérisation analogue ; le théorème de Robertson-Seymour apporte une réponse affirmative. Ce théorème montre qu'un certain classement (partiel) entre les graphes possède des propriétés remarquables (c'est un bel ordre). On en déduit que pour toute famille de graphes « fermée pour les mineurs » (le sens technique exact de cette expression sera détaillé plus loin), il existe une liste finie de graphes « interdits » caractérisant cette famille. Cependant, même pour des familles simples comme celle des graphes toroïdaux, cette liste peut être très longue, et on ne connaît pas en général de méthode explicite pour la construire.

Historique

En 1930, Kazimierz Kuratowski démontrait qu'un graphe était planaire s'il ne contenait pas de sous-graphe qui soit une expansion du graphe complet K₅, ou du graphe biparti complet K_3,3.

En 1937, Klaus Wagner donnait une forme analogue et d'ailleurs équivalente de ce théorème, en caractérisant ces graphes comme ne contenant ni K₅ ni K_3,3 comme « mineurs ». Cette forme permet une généralisation facile à de nombreuses familles de graphes ayant une propriété analogue, par exemple « être traçable sur un tore », c'est pourquoi le théorème des mineurs, avant sa démonstration, était connu sous le nom de conjecture de Wagner (cependant, Wagner a par la suite affirmé qu'il n'avait jamais formulé lui-même cette conjecture, et avait d'ailleurs toujours pensé qu'elle devait être fausse).

Un résultat plus faible que cette conjecture, concernant seulement les arbres, découle du théorème de Kruskal, lequel avait été conjecturé en 1937 par Andrew Vázsonyi ; il fut démontré indépendamment en 1960 par Joseph Kruskal et S. Tarkowski.

Entre 1983 et 2004, Neil Robertson et Paul Seymour développèrent sur une série de vingt articles publiés dans la revue Journal of Combinatorial Theory un plan de démonstration complet consistant entre autres à réduire progressivement le cas général à des cas particuliers plus simples (ainsi, le premier de leurs articles s'intitule Mineurs : exclusion d'une forêt et donne une démonstration d'une vingtaine de pages de ce que si l'un des mineurs exclus est une forêt, le théorème est vrai), mais introduisant également de nombreux concepts et outils nouveaux, comme la théorie de la décomposition arborescente. L'ensemble de la démonstration couvre au total plus de 500 pages ; la communauté mathématique en a validé le résultat, appelé désormais théorème de Robertson-Seymour, pour lequel ils reçurent en 2006 le prix Fulkerson ; ce théorème, les outils développés pour sa démonstration, et ses conséquences algorithmiques inattendues, sont généralement considérés comme parmi les plus importants de la théorie des graphes.

Le théorème de Robertson-Seymour

Définitions préliminaires

Un exemple de deux graphes, dont l'un (celui du dessous) est un mineur de l'autre. Le mineur a été obtenu en supprimant l'arête [e,f] et en contractant l'arête [b,c].

Un mineur d'un graphe non orienté G est un graphe pouvant être obtenu à partir de G par une suite (éventuellement vide) de contractions d'arêtes de G, de suppressions d'arêtes de G, et de suppressions de sommets isolés de G.

La relation « H est un mineur de G » (qu'on notera par la suite H ≤ G) est une relation d'ordre partiel sur l'ensemble des graphes non orientés finis, considérés à isomorphisme près (si l'on ne considère pas les graphes isomorphes comme identiques, la relation n'est plus antisymétrique, et on obtient seulement un préordre).

Un préordre est appelé un beau préordre s'il ne contient aucune suite infinie strictement décroissante (on dit que la relation de préordre est bien fondée), ni aucune antichaîne infinie, c'est-à-dire aucun ensemble infini d'éléments incomparables deux à deux ; dans le cas d'un ordre (partiel), on dit que c'est un bel ordre (cette définition généralise aux ordres partiels la notion de bon ordre définie pour les ensembles totalement ordonnés).

Énoncés du théorème

Les définitions précédentes permettent de formuler rigoureusement le

Théorème de Robertson–Seymour — La relation de préordre « F ≤ G si et seulement si F est un mineur de G » est un beau préordre sur l'ensemble des graphes non orientés finis.

L'existence d'une suite infinie strictement décroissante étant évidemment impossible (puisque chaque mineur contient alors moins d'arêtes que le graphe précédent), ce théorème revient donc à affirmer qu'il n'y a pas d'ensemble infini de graphes deux à deux incomparables par la relation ≤ ; il convient cependant de remarquer que le théorème n'exclut nullement qu'il existe de tels ensembles finis aussi grands que l'on veut.

Utilisant la notion de graphe minimal d'un ensemble, c'est-à-dire tel qu'aucun autre graphe de l'ensemble n'en soit un mineur, on arrive à un énoncé équivalent au théorème, affirmant que dans tout ensemble de graphes, il n'y a (à isomorphisme près) qu'un nombre fini de graphes minimaux ; comme on le verra plus loin, cela revient à caractériser toute famille F « fermée pour les mineurs » par un ensemble fini S de mineurs exclus.

Dire qu'il n'existe pas d'antichaînes infinies revient, par définition, à dire que dans tout ensemble infini de graphes, il existe un couple de graphes dont l'un est un mineur de l'autre ; un résultat plus précis, et qui est en fait une propriété équivalente au théorème de Robertson-Seymour, couvre également l'impossibilité de suites infinies décroissantes, et affirme que toute suite infinie $G_{i}$ de graphes contient un couple $\scriptstyle (G_{i},G_{j})$ tel que i < j et que $G_{i}$ est un mineur de $G_{j}$.

Éléments de la démonstration

La preuve du théorème repose sur une série de résultats publiés entre 1983 et 2004 sous le titre Graph Minors, et dont l'enchaînement est résumé dans l'article Graph Minors XX, mettant un point final à la démonstration. Tous les résultats obtenus dans cette suite de vingt articles ne sont pas nécessaires à la preuve finale, mais une rédaction complète de celle-ci demanderait encore plusieurs centaines de pages ; il est difficile ne serait-ce que d'esquisser les grandes lignes d'une démonstration aussi complexe.

Les deux idées essentielles utilisées par Robertson et Seymour sont, d'une part, la notion de structuration de graphe : il s'agit de techniques consistant à décrire un graphe comme composé (le plus souvent par « recollement ») de graphes plus simples ; d'autre part, l'utilisation de considérations topologiques sur les surfaces sur lesquelles un graphe peut être plongé.

La description plus détaillée qui suit est essentiellement adaptée de celle de Reinhard Diestel, qui suit assez étroitement la démonstration originale, en la simplifiant quelque peu.

• En utilisant les propriétés des beaux ordres, on se ramène d'abord à l'étude d'une famille infinie de graphes n'admettant pas le graphe complet K_n comme mineur ;
• On montre ensuite qu'il existe un ensemble fini de surfaces S_k tel que les graphes de la famille étudiée sont « presque » plongeables dans l'une des S_k, alors que K_n ne s'y plonge pas.
• La conclusion résulte alors d'un raisonnement par récurrence sur le genre des surfaces S_k (leur nombre de « trous »), la base de la récurrence étant, justement, le théorème de Wagner sur les graphes planaires : une décomposition arborescente convenable d'un graphe plongé sur une surface permet de se ramener à une surface de genre inférieur (en « comblant les trous ») sans trop modifier le graphe.

Familles fermées pour les mineurs

Une famille F de graphes est dite fermée (ou close) pour les mineurs (ce qui sera abrégé en famille fermée dans le reste de cet article) si chaque mineur d'un graphe de F appartient également à F. Dans le langage de la théorie des ordres, une famille fermée est donc une section commençante pour la relation « être un mineur ».

Caractérisation par mineurs exclus

Si F est une famille fermée, appelons S l'ensemble des graphes qui ne sont pas dans F (le complémentaire de F). Le théorème de Robertson–Seymour affirme l'existence d'un ensemble fini H formé des éléments minimaux de S. Ces éléments minimaux caractérisent F : les graphes de F sont exactement ceux n'admettant aucun graphe de H comme mineur. Les éléments de H sont appelés les mineurs exclus (ou interdits), ou encore les obstructions, pour la famille F.

Ainsi, les graphes planaires forment une famille fermée : les contractions et les suppressions d'arêtes d'un graphe planaire ne peuvent détruire sa planarité. Il en résulte que ces graphes peuvent être caractérisés par une famille finie de mineurs exclus, qui sont dans ce cas les deux graphes du théorème de Wagner : le graphe complet K₅ et le graphe biparti complet K_3,3.

L'existence d'une caractérisation par mineurs exclus de toutes les familles fermées est une affirmation équivalente au théorème de Robertson-Seymour. En effet, si S est un ensemble de graphes, appelons F la famille des graphes n'ayant pas de mineurs dans S. F est alors fermée, et son ensemble H de mineurs exclus est exactement l'ensemble des éléments minimaux de S (incomparables deux à deux), ce qui prouve que cet ensemble est fini.

Exemples de familles fermées

La famille de Petersen, ensemble des sept obstructions correspondant aux graphes pouvant être plongés dans l'espace sans entrelacements (ces graphes sont incomparables en tant que mineurs, mais reliés les uns aux autres (comme indiqué par les traits bleus) par les transformations Y-Δ du théorème de Kennelly).

Les familles de graphes (finis) suivantes sont fermées pour les mineurs, et par conséquent (d'après le théorème de Robertson–Seymour) possèdent des caractérisations par mineurs exclus (mais qu'on ne connait pas explicitement en général) :

• les forêts (les graphes qui sont des unions d'arbres disjoints) ; on remarquera que les arbres eux-mêmes ne forment pas une famille fermée, un mineur d'un arbre n'étant pas forcément connexe ;
• les graphes planaires, les graphes toroïdaux, et, plus généralement, les graphes qui peuvent être tracés sur une surface donnée ;
• les graphes qui peuvent être plongés sans entrelacement ou sans nœud dans l'espace euclidien à 3 dimensions ;
• les graphes dont certains invariants, tels que la largeur arborescente ou la taille du coupe-cycles de sommets minimum, sont bornés par une constante finie fixée.

Ensembles d'obstructions

L’ensemble des obstructions pour une famille F donnée est défini comme l'ensemble des éléments minimaux (pour la relation de mineurs) du complémentaire de F, c'est-à-dire que c'est le plus petit ensemble de mineurs exclus caractérisant F ; le théorème de Robertson-Seymour affirme que cet ensemble est toujours fini quelle que soit F.

Des exemples d'ensembles d'obstructions finis étaient déjà connus (pour des classes de graphes particuliers) avant que le théorème de Robertson–Seymour soit démontré. Ainsi, la famille des forêts a pour seule obstruction le cycle à trois sommets (si l'on se restreint aux graphes simples), c'est-à-dire qu'un graphe est une forêt si et seulement s'il n'a pas ce cycle pour mineur. De même, le théorème de Wagner dit que l'ensemble des obstructions pour les graphes planaires est {K₅, K_3,3}. Un théorème analogue caractérise les graphes planaires extérieurs comme ayant pour obstructions les graphes K₄ et K_2,3.

Le théorème de Robertson-Seymour étend ces résultats à des familles fermées quelconques, mais, étant extrêmement non constructif, ne permet le plus souvent pas, même en principe, de déterminer l'ensemble des obstructions d'une famille donnée. Par exemple, l'ensemble des graphes toroïdaux (traçables sur un tore) est une famille fermée dont on ignore l'ensemble des obstructions ; on sait seulement qu'il comporte au moins 17 000 graphes. En 2020, on ne connait complètement l'ensemble des obstructions pour les familles de graphes traçables sur une surface donnée que dans le cas du plan (les deux graphes mentionnés plus haut) et dans le cas du plan projectif, où cet ensemble comporte 35 graphes.

Algorithmes liés au théorème des mineurs

De nombreuses questions d'informatique théorique sont modélisées par des graphes, ou plus précisément par la détermination de propriétés de certains graphes, un exemple célèbre étant le problème du voyageur de commerce.

La démonstration du théorème des mineurs a complètement changé l'estimation qu'on avait de la difficulté algorithmique de certains de ces problèmes. Ainsi, on ignorait jusque-là si la question de savoir si un graphe peut être plongé sans nœuds dans l'espace usuel était calculable, c'est-à-dire décidable par une machine de Turing ; on sait désormais qu'en fait, ce problème appartient à la classe P des problèmes solubles en temps polynomial, bien qu'on ne connaisse toujours aucun algorithme (même très lent) pour le résoudre.

Reconnaissance en temps polynomial

Robertson et Seymour ont démontré que pour tout graphe fixé G, il existe un algorithme en temps polynomial qui teste si un graphe quelconque H possède G comme mineur. Plus précisément, cet algorithme demande un temps proportionnel au cube du nombre n des sommets et arêtes du graphe testé H (ce que l'on note $O(n^{3})$ en notation de Landau). Ce résultat est moins utile en pratique qu'on ne pourrait le croire, parce que la constante de proportionnalité croît avec la taille de G de manière exponentielle. Il en résulte cependant que, pour toute famille fermée F, il existe un algorithme en temps polynomial décidant si un graphe donné G appartient ou non à F : il suffit de contrôler, pour chaque élément de l'ensemble des obstructions de F, s'il est ou non un mineur de G.

L'existence de cet algorithme est donc une conséquence du théorème de Robertson-Seymour, mais ce dernier ne donne aucun moyen effectif de le construire ; il est ainsi possible de démontrer qu'un problème peut être résolu en temps polynomial (dans le langage de la théorie de la complexité, on dit qu'il appartient à la classe P) sans pouvoir exhiber une telle solution : on dit qu'une telle preuve est non constructive. En revanche, dans de nombreux cas où l'ensemble des obstructions de F est connu explicitement, il est possible de savoir si un graphe appartient à F de manière plus efficace encore ; ainsi, tester si un graphe à n sommets est planaire peut être fait en temps linéaire, c'est-à-dire en temps proportionnel à n.

Pour des invariants de graphes ayant la propriété que, pour un k fixé, la famille des graphes d'invariant plus petit que k est fermée, le même théorème s'applique ; c'est par exemple le cas de la largeur arborescente, ou du genre minimal de la surface sur laquelle le graphe peut être tracé. Dans chacun de ces cas, pour chaque k fixé, il y a un algorithme permettant, pour un graphe G ayant n sommets et arêtes, de déterminer si son invariant est ou non inférieur à k, en un temps inférieur à $C(k)n^{3}$, où $C(k)$ est une constante ne dépendant que de k et de l'invariant mesuré. Un problème ayant cette propriété (où $n^{3}$ est remplacé par un polynôme quelconque) est dit soluble à paramètre fixé.

Cependant, cette méthode ne permet pas de construire un algorithme unique permettant de déterminer la valeur d'un tel invariant pour un graphe donné (lorsque cette valeur n'est pas bornée à l'avance), à cause de la difficulté qu'il y a à déterminer l'ensemble des obstructions. De plus, la constante $C(k)$ augmente en général extrêmement vite avec k, rendant ces algorithmes très inefficaces en pratique. C'est pourquoi le développement d'algorithmes plus efficaces pour ces problèmes constitue encore en 2020 un important domaine de recherche.

Relation avec le problème P ≟ NP

Le théorème des mineurs semble permettre de construire des algorithmes rapides (polynomiaux, et même cubiques) de résolution de problèmes dont on sait qu'ils sont NP-complets, voire NP-difficiles. Cependant, une analyse plus précise de la définition de la complexité des algorithmes montre que ces algorithmes prennent en fait un temps exponentiel par rapport à la taille des graphes décrivant le problème à résoudre. Ainsi, le problème des chemins disjoints est NP-complet, mais Robertson et Seymour ont montré que, à k fixé, le problème des k chemins disjoints est effectivement soluble en temps polynomial ; cette contradiction apparente se résout en remarquant que le temps pris par l'algorithme est un polynôme en n (la taille du graphe étudié) de la forme $C(k)n^{3}$, comme on l'a vu dans la section précédente, mais que la constante $C(k)$ augmente au moins exponentiellement avec k, et que c'est elle qui définit la complexité du problème lorsque k est inconnu.

Bien que le théorème de Robertson-Seymour n'ait pas vraiment apporté d'informations nouvelles concernant le problème P ≟ NP, Fellows et Langston ont fait remarquer que leur démonstration non constructive d'existence d'algorithmes polynomiaux (et où apparaissent souvent, qui plus est, des constantes de proportionnalité bien trop grandes pour qu'ils puissent avoir une utilité pratique quelconque) rend moins claire qu'auparavant la distinction entre algorithmes polynomiaux (considérés comme utilisables de manière réaliste) et non polynomiaux (à jamais inutilisables pour des ensembles de données un peu vastes), et donc que l'intuition de la majorité des informaticiens, selon laquelle la classe P est différente de la classe NP, pourrait bien se révéler fausse, sans pour autant que les problèmes NP-complets en deviennent faciles à résoudre.

Conséquences en logique mathématique

L'étude de la logique mathématique, c'est-à-dire l'analyse systématique des fondations des mathématiques et des bases logiques sur lesquelles s'appuient les démonstrations, commencée à la fin du dix-neuvième siècle par des logiciens et des mathématiciens tels que Gottlob Frege et Giuseppe Peano, a amené vers 1930 à la découverte de surprenants résultats d'indécidabilité, liés aux célèbres théorèmes d'incomplétude de Gödel ; ces résultats, dont la forme générale est « la théorie T ne permet, pour un certain énoncé E exprimable dans son langage, ni de démontrer E, ni de démontrer sa négation non E », sont souvent dits méta-mathématiques, car ils portent sur les mathématiques elles-mêmes et non sur les objets mathématiques usuels. La plupart des énoncés E ainsi construits étaient généralement jugés artificiels, et des énoncés plus conformes à la pratique courante des mathématiciens semblaient ne pas devoir susciter de tels problèmes. Pourtant, vers 1980, Jeff Paris a obtenu des énoncés de forme apparemment naturelle et inoffensive, par exemple affirmant qu'une certaine suite finit par décroître, mais revenant en fait à définir des entiers si grands que leur « existence » ne peut être prouvée à l'aide des seuls axiomes de Peano ; cela implique que, en n'utilisant que ces axiomes, les énoncés en question sont indécidables.

En 1987, Friedman, Robertson et Seymour ont montré que, si le théorème des mineurs était vrai, le théorème suivant (qui en est un cas particulier) serait lui aussi, et pour les mêmes raisons, non démontrable dans des systèmes beaucoup plus forts que l'arithmétique de Peano, bien qu'il soit démontrable dans ZFC (et en fait, l'analyse détaillée de la preuve de Robertson et Seymour permet de montrer qu'il est démontrable dans des systèmes nettement moins puissants que ZFC) :

Théorème : Pour tout entier n, il existe un entier m si grand que si G₁, ..., G_m est une suite de graphes finis non orientés, où chaque G_i a au plus n+i sommets et arêtes, alors il existe j < k tels que G_j soit un mineur de G_k.

Là encore, l'entier m est une fonction de n à croissance si rapide que les axiomes de Peano (ou même des formes très renforcées de ces axiomes) ne permettent pas de montrer qu'elle est toujours définie, ce qui explique ces résultats d'indécidabilité ; on trouvera dans l'article théorème de Kruskal une description plus précise d'autres théorèmes de logique mathématique analogues, dus eux aussi à Friedman. Ces théorèmes donnent ainsi des exemples de propositions indécidables en arithmétique, considérées comme plus naturelles que celles correspondant au théorème de Gödel.

Généralisations : hypergraphes et graphes infinis

En 2011, Robertson et Seymour ont achevé la démonstration d'un résultat analogue sur les hypergraphes, définissant un préordre généralisant la relation de mineur, et montrant qu'il s'agit là encore d'un bel ordre. Parmi les conséquences de ce résultat, ils en déduisent que le théorème des mineurs (pour les graphes) s'applique encore si on munit les sommets ou les arêtes d'étiquettes (elles-mêmes ordonnées par un bel ordre), et qu'on demande aux mineurs de respecter l'ordre de ces étiquettes. Ce résultat leur a également permis de démontrer une conjecture de Nash-Williams : dans toute suite infinie de graphes, il en existe deux tels que le premier peut être immergé dans le second.

Il n'est pas impossible qu'un théorème analogue soit encore vrai pour des graphes infinis dénombrables, mais cette conjecture (ou d'ailleurs sa réfutation) est considérée comme encore plus difficile que ne l'est le théorème des mineurs ; Reinhard Diestel pense qu'elle pourrait être liée à une autre conjecture de Seymour, affirmant que tout graphe infini dénombrable possède un mineur (strictement plus petit) qui lui est isomorphe. En revanche, on sait que ces résultats sont faux pour des graphes non dénombrables : Péter Komjáth (en) a démontré que, si $\lambda$ est un cardinal non dénombrable, il existe $2^{\lambda }$ graphes de cardinal $\lambda$ dont aucun n'est un mineur d'un autre, et Bogdan Oporowski a obtenu un contre-exemple à la conjecture de Seymour dans le cas non dénombrable.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Robertson–Seymour theorem » (voir la liste des auteurs).

Bibliographie

Livres

• (en) Daniel Bienstock et Michael A. Langston, « Algorithmic implications of the graph minor theorem », dans Network Models, coll. « Handbooks in Operations Research and Management Science » (n^o 7), 1995 (DOI 10.1016/S0927-0507(05)80125-2, lire en ligne [PDF]), p. 481–502.
• (en) John Chambers, Hunting for torus obstructions, M.Sc. thesis, Department of Computer Science, UVic, 2002.
• (en) Reinhard Diestel, « Minors, Trees, and WQO », dans Graph Theory, Springer, 2005 (lire en ligne [PDF]), p. 326–367.
• (en) Harvey Friedman, Neil Robertson et Paul Seymour, « The metamathematics of the graph minor theorem », dans S. Simpson, Logic and Combinatorics, AMS, coll. « Contemporary Mathematics » (n^o 65), 1987, p. 229–261.

Articles scientifiques

• Jean-Paul Delahaye, « Une propriété cachée des graphes », Pour la science, vol. avril, n^o 3,‎ 2008, p. 92-97.
  Article de vulgarisation.
• Bruno Courcelle, « Structuration des graphes et logique », Leçons de mathématiques d'aujourd'hui, vol. 4,‎ 2010, p. 167-194.
  Leçon rédigée par Fabrice Bazzaro.
• (en) László Lovász, « Graph Minor Theory », Bull. Amer. Math. Soc. (New Series), vol. 43, n^o 1,‎ 2005, p. 75–86 (lire en ligne [PDF]).
• (en) Michael R. Fellows et Michael A. Langston, « Nonconstructive tools for proving polynomial-time decidability », Journal of the ACM, vol. 35, n^o 3,‎ 1988, p. 727–739 (DOI 10.1145/44483.44491).
• (en) Michael R. Fellows et Michael A. Langston, « On search, decision, and the efficiency of polynomial-time algorithms », Journal of Computer and System Sciences, vol. 49, n^o 3,‎ 1994, p. 769–779.
  En voici un résumé étendu [PDF], dû aux auteurs eux-mêmes.
• (en) Neil Robertson et Paul Seymour, « Graph Minors. I. Excluding a forest », Journal of Combinatorial Theory, Series B, vol. 35, n^o 1,‎ 1983, p. 39–61 (DOI 10.1016/0095-8956(83)90079-5).
  Le premier des vingt articles de la démonstration complète, intitulé Mineurs : exclusion d'une forêt.
  En 1995, Reinhard Diestel a publié une preuve simplifiée de ce résultat, dans un article de quatre pages [PDF].
• (en) Neil Robertson et Paul Seymour, « Graph Minors. XIII. The disjoint paths problem », Journal of Combinatorial Theory, Series B, vol. 63, n^o 1,‎ 1995, p. 65–110 (DOI 10.1006/jctb.1995.1006).
• (en) Neil Robertson et Paul Seymour, « Graph Minors. XX. Wagner's conjecture », Journal of Combinatorial Theory, Series B, vol. 92, n^o 2,‎ 2004, p. 325–357 (lire en ligne [PDF]).
• (en) Neil Robertson et Paul Seymour, « Graph Minors. XXIII. Nash-Williams’s immersion conjecture », Journal of Combinatorial Theory, Series B, vol. 100, n^o 2,‎ 2010, p. 181–205 (lire en ligne [PDF]).

Liste complète des vingt-trois articles de Robertson et Seymour

Ces articles (à l'exception de Graph minors. II) sont tous parus dans le Journal of Combinatorial Theory (Series B), mais pas toujours exactement dans l'ordre de leur numérotation (entre parenthèses, une traduction française approximative du titre).

• Graph minors. I. Excluding a forest, J. Combin. Theory, Ser. B, 35 (1983), 39–61. (Exclusion d'une forêt)
• Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7 (1986), 309–322. (Aspects algorithmiques de la largeur arborescente)
• Graph minors. III. Planar tree-width, J. Combin. Theory, Ser. B, 36 (1984), 49–64. (Largeur arborescente dans le cas planaire)
• Graph minors. IV. Tree-width and well-quasi-ordering, J. Combin. Theory, Ser. B, 48 (1990), 227–254. (Bel ordre et largeur arborescente)
• Graph minors. V. Excluding a planar graph, J. Combin. Theory, Ser. B, 41 (1986), 92–114. (Exclusion d'un graphe planaire)
• Graph minors. VI. Disjoint paths across a disc, J. Combin. Theory, Ser. B, 41 (1986), 115–138. (Chemins disjoints à travers un disque)
• Graph minors. VII. Disjoint paths on a surface, J. Combin. Theory, Ser. B, 45 (1988), 212–254. (Chemins disjoints sur une surface)
• Graph minors. VIII. A Kuratowski theorem for general surfaces, J. Combin. Theory, Ser. B, 48 (1990), 255–288. (Un théorème de Kuratowski pour des surfaces générales)
• Graph minors. IX. Disjoint crossed paths, J. Combin. Theory, Ser. B, 49 (1990), 40–77. (Chemins disjoints croisés)
• Graph minors. X. Obstructions to tree-decomposition, J. Combin. Theory, Ser. B, 52 (1991), 153–190. (Obstructions à une décomposition arborescente)
• Graph minors. XI. Circuits on a surface, J. Combin. Theory, Ser. B, 60 (1994), 72–106. (Circuits sur une surface)
• Graph minors. XII. Distance on a surface, J. Combin. Theory, Ser. B, 64 (1995), 240–272. (Distance sur une surface)
• Graph minors. XIII. The disjoint paths problem, J. Combin. Theory, Ser. B, 63 (1995), 65–110. (Le problème des chemins disjoints)
• Graph minors. XIV. Extending an embedding, J. Combin. Theory, Ser. B, 65 (1995), 23–50. (Extension d'un plongement)
• Graph minors. XV. Giant steps, J. Combin. Theory, Ser. B, 68 (1996), 112–148. (Des pas de géant)
• Graph minors. XVI. Excluding a non-planar graph, J. Combin. Theory, Ser. B, 89 (2003), 43–76. (Exclusion d'un graphe non planaire)
• Graph minors. XVII. Taming a vortex, J. Combin. Theory, Ser. B, 77 (1999), 162–210. (Apprivoiser un sommet)
• Graph minors. XVIII. Tree-decompositions and well-quasi-ordering, J. Combin. Theory, Ser. B, 89 (2003), 77–108. (Décomposition arborescente et bel ordre)
• Graph minors. XIX. Well-quasi-ordering on a surface, J. Combin. Theory, Ser. B, 90 (2004), 325–385. (Bel ordre sur une surface)
• Graph minors. XX. Wagner’s conjecture, J. Combin. Theory, Ser. B, 92 (2004), 325–357. ((en) texte intégral [PDF]) (La conjecture de Wagner)
• Graph minors. XXI. Graphs with unique linkages, J. Combin. Theory, Ser. B, 99 (2009), 583–616. ((en) texte intégral [PDF]) (Graphes à liens uniques)
• Graph minors. XXII. Irrelevant vertices in linkage problems, J. Combin. Theory, Ser. B, (2011, sous presse). ((en) texte intégral [PDF]) (Sommets n'intervenant pas dans le problème des liens)
• Graph minors. XXIII. Nash-Williams’s immersion conjecture, J. Combin. Theory, Ser. B, 100 (2010), 181–205. ((en) texte intégral [PDF]) (La conjecture de plongement de Nash-Williams)

 

Voir aussi

Articles connexes

• Bel ordre
• Graphe planaire
• Lemme de Higman
• Théorème de Kruskal

Liens externes

• Sur le « site professionnel de Eric Thierry » (maître de conférences à l'ENS Lyon), on trouvera en particulier un exposé rigoureux de Bastien Legloannec, en français [PDF], contenant des démonstrations complètes des propriétés des beaux ordres (en passant par le théorème de Ramsey infini, qu'il démontre également), une démonstration du théorème de Kruskal dans le cas des arbres non étiquetés, et beaucoup d'exemples et de contre-exemples.