Some New Results on the Well-Quasi-Ordering of Graphs

Resume Quelques resultats nouveaux sur la relation de bel ordre des graphes finis. Designons par l'ensemble des graphes finis, et, lorsque G, H , ecrivons H ⊆ G si H est isomorphe a un mineur de G, c'est-a-dire a une contraction d'un sous-graphe partiel de G. Dans les annees 1960, K. WAGNER a fait la conjecture (non publiee) que est belordonne par cette relation d'inclusion. Pour des graphes finis, cela signifie que dans tout sous-ensemble infini un certain graphe sera isomorphe a un mineur donne d'un autre graphe. Recemment, les auteurs de cet article ont demontre des theoremes qui laissent fortement presager que la conjecture de WAGNER est correcte. Notre methode consiste a montrer que l'ensemble des graphes G qui ne contiennent pas un certain graphe fixe H comme mineur a une structure deinie, et de montrer alors, qu'etant donnee cette structure, l'ensemble des graphes qui la possedent est belordonne. Si on savait le faire pour tout graphe H, il en decoulerait que ( ,⊆) est lui-měme belordonne, done que la conjecture de WAGNER est vraie. La structure de graphes mentionnee plus haut est construite en trois etapes: (1) plonger un graphe dans une surface S; (2) adjoindre au plus n sommets, qui peuvent ětre adjacents a n'importe quels des autres sommets, et (3) joindre les unes aux autres des copies disjointes de tels graphes en une structure d'arbre. Ici, S et n sont determines par le graphe H exclu, et les graphes adjacents dans la structure d'arbre formant G sont joints en identifiant des sous-ensembles de leurs sommets d'une maniere univoque. De tels sous-ensembles ne peuvent intersecter la surface de plongement S que trivialement, c'est-a-dire au plus en trois sommets contenus dans la frontiere d'une face du plongement. Ce programme a maintenant ete execute pour des classes de graphes G qui ne contiennent pas comme mineur un graphe planaire fixe H; c'est un cas ou il n'est pas necessaire d'utiliser la structure de la surface. Pour tout graphe planaire H, il existe un entier w tel que tout graphe G qui ne contient pas H comme mineur peut ětre construit en joignant en une structure d'arbre des graphes avec au plus w sommets. De plus, on montre que les classes de graphes G qui peuvent ětre construites de cette maniere sont belordonnees; dans cette demonstration on utilise une generalisation du theoreme de KRUSKAL sur la structure d'arbre, que l'on prouve pour des structures d'arbre de certains hypergraphes structures (families d'ensem-bles) de dimension bornee. Les consequences de ce travail sont: (1) que toutes les anti-chaines (ensembles d'elements non relies deux a deux) dans ( ,⊆) qui contiennent au moins un graphe planaire H sont finies, et (2) qu'il existe un algorithme pour determiner la relation H ⊆ G (H est isomorphe a un mineur de G) lorsque H est un graphe planaire fixe et G ∈ , avec temps de calcul borne par des polynomes de la dimension de G. Nous pensons que nos methodes nous permettront de demontrer la conjecture generale structurelle ainsi qu'un theoreme de bel ordre, avec les deux měmes consequences qu'auparavant sans la condition que H soit planaire, c'est-a-dire de demontrer la conjecture de WAGNER et d'obtenir un bon algorithme pour determiner la relation H ⊆ G pour tout G∈ Abstract It has been conjectured by K. WAGNER that finite graphs are well-quasi-ordered by minor inclusion, i.e. being isomorphic to a contraction of a subgraph. A method is reported on here that shows promise of settling this conjecture. We have proved (1) that all graphs G not including a fixed planar graph H as a minor can be constructed by piecing together graphs on a bounded number of vertices in a tree-structure, and (2) by elaborating the KRUSKAL tree theorem that the class of graphs formed by piecing together graphs of bounded size in tree-structures is well-quasi-ordered. It follows from this that no infinite antichain of finite graphs can include even one planar graph and that there is a “good” algorithm for testing the presence of a fixed planar graph as a minor.