Etude des classes de graphes et de matroïdes closes par mineur

Classes de graphes et de matroïdes closes par mineur

   Soit C une classe de graphe. On dit que C est une classe de graphes close par mineur si pour tout graphe G ∈ C , tous les mineurs de G appartiennent à C . Un mineur exclu pour la classe C est un graphe E tel que E 6∈ C et pour tout mineur strict (i.e. un mineur strictement plus petit) H de E, H ∈ C . De nombreuses et importantes classes de graphes sont closes par mineur, notamment les graphes planaires (et plus généralement les graphes plongeables dans les surface) ainsi que certaines classes de graphes topologiques (arbres, graphes planaires externes, graphes sans entrelacs, sans noeuds,…). Un bel ordre ≤ sur un ensemble X est un ordre partiel sur X tel que, pour toute suite (xi)i∈N d’éléments de X, il existe i et j tels que i < j et xi ≤ xj . On dira qu’une classe est {bien-quasi-ordonnée} pour la relation ≤ si ≤ est un bel ordre pour cette classe. Une question importante était de savoir si la relation de mineur formait un bel ordre pour la classe des graphes. Kruskal a montré que c’était le cas pour les arbres.
Théorème 2.1 (Kruskal, 1960, [43]) Les arbres finis sont bien-quasi-ordonnés par la relation de mineur. Mais le théorème fondamental dans la théorie des mineurs de graphes est le suivant, qui généralise le théorème précédent à l’ensemble des graphes.
Théorème 2.2 (Robertson & Seymour, 2004, [59]) Les graphes sont bien-quasi-ordonnés pour la relation de mineur. En particulier cela implique l’inexistence d’antichaînes infinies où une antichaîne est dans ce cas un ensemble de graphes A tels que pour tout H et G dans A, si H est un mineur de G alors les graphes H et G sont isomorphes. Autrement dit, il ne peut exister un ensemble infini d’éléments incomparables pour la relation de mineur. On peut donc reformuler le Théorème 2.2 de la manière suivante.
Théorème 2.3 (Robertson & Seymour, 2004, [59]) Toute classe de graphe close par mineur est caractérisée par un ensemble fini de mineurs exclus. Néanmoins la preuve de ce théorème n’est pas constructive et ne permet donc pas de donner la liste des mineurs exclus. La liste est connue uniquement pour certaines classes de graphes closes par mineur. On donne un petit aperçu de telles caractérisations.
Théorème 2.4 (Folklore) Un graphe est un arbre si et seulement s’il ne contient pas K3 comme mineur.
Théorème 2.5 (Chartrand & Harary, 1967, [16]) Un graphe est planaire externe si et seulement s’il ne contient pas K4 ou K2,3 comme mineur. La liste ne serait pas complète sans la célèbre caractérisation des graphes planaires dûe à Kuratowski et Wagner.

Mineurs enracinés

   Dans cette partie, nous allons étudier un type différent de mineurs : les mineurs enracinés. Soit G un graphe et {v1, v2,…, vk} des sommets distincts de G et soit H un graphe sur l’ensemble {v1, v2,…, vk}. On dit que G contient un mineur H enraciné en {v1, v2,…, vk} s’il existe des sous-graphes connexes H1,H2,…,Hk tels que vi ∈ Hi pour tout 1 ≤ i ≤ k et Hi est adjacent à Hj si et seulement si vi et v j sont adjacents dans H. Pour les graphes H suffisamment petits, l’existence de tels mineurs enracinés peut être caractérisée complètement. Par exemple dans le cas de mineurs enracinés K3, le théorème suivant donne une condition nécessaire et suffisante d’existance d’un tel mineur.
Théorème 2.33 (Wood & Linusson, [82]) Soit a,b,c trois sommets distints d’un graphe connexe G, alors soit :
– G contient un mineur K3 enraciné en {a,b,c}, ou
– il existe un sommet v ∈ V(G) tel que au plus un élément de {a,b,c} appartient à chaque chaque composante connexe de G \ v. Un théorème similaire peut être obtenu dans le cas des mineurs enracinés K4. Le théorème suivant est dû à Robertson et Seymour et Thomas [60] mais une caractérisation équivalente peut être trouvée dans un article de Fabila-Monroy et Wood [26] ainsi que chez Robertson et Seymour [57].
Théorème 2.34 (Robertson, Seymour & Thomas, 1996, [60]) Soit G un graphe et v1, v2, v3, v4 des sommets de G, alors soit
– G contient un mineur K4 enraciné en {v1, v2, v3, v4}, ou
– il existe une 3-séparation (A,B) de G avec {v1, v2, v3, v4} ⊆ A, et |B \ A| ≥ 2, ou
– G peut être plongé dans un disque où v1, v2, v3, v4 sont sur le bord du disque dans cet ordre. Le problème de trouver un mineur enraciné est relié directement au problème de l’existence de chemins disjoints entre certaines paires de sommets. On dit qu’un graphe est k-linked si pour tout ensemble de 2k sommets distincts s1,s2,…,sk,t1,t2,…,tk, il existe des chemins disjoints P1,P2,…,Pk tels que les extrémités de Pi soient si et ti respectivement pour tout 1 ≤ i ≤ k.

Conclusion

  Nous avons étudié, tout au long du Chapitre 3, certaines conditions suffisantes pour qu’un graphe admette un mineur Kt. Nous résumons ici ces résultats et les questions ouvertes qui en découlent.
– Le Théorème 3.4 affirme que tout graphe sans mineur Kt pour t ≤ 7 contient une arêtequi appartient à au plus t − 3 triangles et que cette arête est incidente à un sommet de petit degré. Ce théorème généralise un résultat de Nevo pour le cas t = 6 et l’étend pour le cas t = 7.
– Les Théorèmes 3.5, 3.6 et 3.7 étendent différents aspects du Théorème 3.4 au cas supérieur (t = 8). En effet, le Théorème 3.4 ne peut étre étendu directement au cas t = 8 car certains contre-exemples construits à partir de copies de K2,2,2,2,2 apparaissent, et seuls certains aspects de ce théorème peuvent être généralisés. Pour le cas t = 9, nous avons proposé les Conjectures 3.48, 3.49 et 3.50 comme une possible extension des résultats obtenus dans le cas t = 8. La preuve du cas t = 8 fait intervenir une étude exhaustive des voisinages d’un sommet de petit degré dans un contre exemple minimal au théorème. Cette étude exhaustive à été effectuée par ordinateur et il n’est pas clair qu’une telle étude puisse être réalisée dans le cas t = 9 dû à l’explosion du nombre de voisinages possibles. Il serait aussi intéressant, pour les cas t = 7 et t = 8, de trouver une preuve n’utilisant pas cette étude exhaustive des voisinages. Pour les petit cas, la seule possibilité, pour le moment, reste d’utiliser les théorèmes de caractérisation des graphes sans mineur Kt (pour t ≤ 5). L’existence d’un théorème de caractérisation pour les graphes sans mineur Kt pour t ≥ 6 étant un problème ouvert très difficile, il serait intéressant de trouver une preuve structurelle sans énumération des voisinages pour ces théorèmes. Du côté des matroïdes, le Théorème 3.8 montre que l’on peut généraliser les résultats sur les graphes aux matroïdes. Néanmoins le problème se révèle bien plus ardu que dans le cas des graphes. Nous avons posé la question de savoir si tout matroïde dont les éléments appartiennent à t triangles contient nécessairement un mineur parmi une liste finie (cf. Question 3.51). Répondre à cette question serait une avancée considérable sur ce problème même si l’on se réduit au cas des matroïdes graphiques. Dans les cas où t est petit, il serait intéressant de trouver un analogue au Théorème 3.8. La question est ouverte pour t ≥ 4 mais même dans le cas où t = 4, nous n’avons pour le moment pas d’idée sur ce que pourrait être une liste complète de mineurs interdits. Notons que dans le cas du Théorème 3.8, la preuve utilise un théorème de caractérisation des matroïdes binaires sans mineur F7 dû à Seymour. Il serait intéressant de trouver une preuve ne faisant pas appel à ce théorème. En effet il est peu probable que de tels théorèmes se généralisent aisément. Trouver une preuve de ce théorème sans utiliser le théorème de Seymour permettrait peut-être de généraliser ces théorèmes aux cas supérieurs. Dans le Chapitre 4, nous avons vu plusieurs applications des théorèmes précédents à plusieurs domaines en théorie des graphes. En particulier, nous avons montré que les graphes sans mineurs K7 étaient génériquement sans 5-stress et que les graphes sans mineur K8 et K2,2,2,2,2 étaient génériquement sans 6 stress.

Table des matières

Introduction
1 Préliminaires
1.1 Graphes 
1.1.1 Connexité et séparations
1.1.2 Quelques classes de graphes
1.1.3 Clique-sum
1.2 Matroïdes 
1.2.1 Quelques classes de matroïdes
1.2.2 Quelques matroïdes particuliers
1.2.3 k-somme de matroïdes
2 Mineurs de graphes et de matroïdes 
2.1 Introduction 
2.2 Classes de graphes et de matroïdes closes par mineur
2.3 Classes de graphes et de matroïdes excluant un certain mineur
2.4 Mineurs enracinés 
2.5 Théorie extrémale et dégénérescence des classes de graphes closes par mineur 
2.6 Invariant de Colin de Verdière
3 Triangles et mineurs de graphes 
3.1 Introduction
3.2 Preuve du Théorème 3.4 
3.2.1 Preuve des cas r = 3, 4, 5, 6
3.2.2 Preuve du cas r = 7 : le cas à 5 triangles
3.3 Preuve des Théorèmes 3.5, 3.6 et 3.7
3.3.0.1 Preuve du Théorème 3.5
3.3.0.2 Preuve du Théorème 3.7
3.3.0.3 Preuve du Théorème 3.6
3.4 Preuve des généralisations aux matroïdes
3.4.1 Preuve du Théorème 3.8
3.4.2 Preuve du Théorème 3.9
3.4.3 Preuve du Théorème 3.10
3.5 Conclusion 
4 Applications 
4.1 Densité globale de triangles
4.2 Rigidité et contraintes dans les graphes 
4.3 Coloration des graphes 
4.3.1 Preuve du Théorème 4.14
4.3.2 Preuve du Théorème 4.15
4.4 Conjecture d’Hadwiger doublement-critique
5 Sur une conjecture de Barát et Thomassen 
5.1 Introduction 
5.2 Préliminaires
5.3 Preuve de la Conjecture 5.1
5.3.1 Aperçu
5.3.2 L’existence de I
5.3.3 L’existence de B, G et R
5.3.4 Réorienter B
5.3.5 Orienter G et I
Conclusion
Bibliographie
A Annexes
A.1 Génération de graphes avec Sage
A.1.1 Recherche d’un mineur de graphe complet
A.1.2 Génération des graphes excluant un certain mineur
A.1.3 Recherche de la taille maximale d’une séparation
A.1.4 Recherche du nombre de triangles par arêtes
A.2 Liste de graphes
A.2.1 Graphes de taille 8 et 9 de degré minimum 4 sans mineur K6
A.2.1.1 Graphes de taille 8
A.2.1.2 Graphes de taille 9
A.3 Mineurs 3-connexe de S(5, 6, 12)

Télécharger le rapport complet