# Beaux ordres et graphes

Jean-Florent Raymond

► To cite this version:

Jean-Florent Raymond. Beaux ordres et graphes. Journées du GDR-IM 2016, 2016, Paris, France. 2016. lirmm-01488486

HAL Id: lirmm-01488486

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01488486v1

Submitted on 13 Mar 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# BEAUX ORDRES ET GRAPHES

Jean-Florent Raymond

Université de Montpellier (LIRMM) et Université de Varsovie

## Introduction

<figure><img src="image_2.png" /></figure>

## Résultats

La contraction d'une arête revient à identifier ses extrémités. On dit que $H$ est mineur induit de $G$ si on peut l'obtenir en contractant les arêtes d'un sous-graphe induit de $G$. Par exemple :

<figure><img src="image_3.png" /></figure>

est mineur de

<figure><img src="image_4.png" /></figure>

mais pas mineur induit.

<figure><img src="image_5.png" /></figure>

est mineur induit de

<figure><img src="image_6.png" /></figure>

mais pas sous-graphe induit.

### Théorème (Błasiok, Kamiński, R., Trunck, 2015)

La classe des graphes ne contenant pas $H$ comme mineur induit est bellement ordonnée par la relation de mineur induit ssi $H$ est mineur induit de $\triangle$ ou de $\blacktriangle$.

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

### Théorème (Błasiok, Kamiński, R., Trunck, 2015)

La classe des graphes ne contenant pas $H$ comme contraction est bellement ordonnée par la relation de contraction ssi $H$ est contraction de $\blacktriangle$.

<figure><img src="image_9.png" /></figure>

### Théorème (Kamiński, R., Trunck, 2014)

Une classe de multigraphes $\mathcal{G}$ est bellement ordonnée par la relation de contraction ssi tous ses éléments ont

* au plus $p$ composantes connexes ; et

* pas de coupe minimale de plus de $k$ arêtes, pour deux entiers $p$ et $k$ fixés.

### Technique de preuve

On veut montrer que $(\mathcal{G}, \leq)$ est un bel ordre :

1. on choisit une bijection $f: \mathcal{G} \to \mathcal{S}$ où $\mathcal{S}$ est une classe qu'on connaît bien ($n$-uplets, mots, arbres, etc.);

2. on choisit un ordre $\leq$ sur $\mathcal{S}$ tel que $f(x) \leq f(y) \iff x \leq y$;

3. on prouve que $(\mathcal{S}, \leq)$ est un bel ordre en utilisant les résultats classiques, ce qu'on peut faire si on a bien choisi $\mathcal{S}$.

Ces trois étapes suffisent, car si on trouvait dans $(\mathcal{G}, \leq)$ une séquence infinie décroissante (ou d'éléments incomparables), on pourrait en déduire une dans $(\mathcal{S}, \leq)$ grâce à la deuxième étape.

La première étape est facilitée si on connaît la *structure* des éléments de $\mathcal{G}$ (théorèmes de décomposition).

## Ordres et graphes

Quels ordres sur les graphes sont de beaux ordres, en général ?

**beaux** : mineurs et immersions (Robertson & Seymour) ;

**pas beaux** : sous-graphes (induits ou non), contractions, mineurs induits, mineurs topologiques (induits ou non) ;

**problèmes ouverts** : immersions induites et immersions fortes.

Quand un ordre n'est pas beau en général, on peut s'intéresser aux classes où il est beau.

## Bibliographie

* J. Błasiok, M. Kamiński, J.-F. Raymond et T. Trunck. Induced mineurs and well-quasi-ordering. *Electronic Notes in Discrete Mathematics*, 49:197 – 201, 2015. The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015 et arXiv:1510.07135.

* M. Kamiński, J.-F. Raymond et T. Trunck. Multigraphs without large bonds are well-quasi-ordered by contraction. *arXiv:1412.2407*, Décembre 2014.

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>