Induced minors and well-quasi-ordering

Abstract : A graph H is an induced minor of a graph G if it can be obtained from an induced subgraph of G by contracting edges. Otherwise, G is said to be H-induced minor-free. Robin Thomas showed in [Graphs without K 4 and well-quasi-ordering, Journal of Combinatorial Theory, Series B, 38(3):240 – 247, 1985] that K 4-induced minor-free graphs are well-quasi ordered by induced minors. We provide a dichotomy theorem for H-induced minor-free graphs and show that the class of H-induced minor-free graphs is well-quasi-ordered by the induced minor relation if and only if H is an induced minor of the gem (the path on 4 vertices plus a dominating vertex) or of the graph obtained by adding a vertex of degree 2 to the complete graph on 4 vertices. Similar dichotomy results were previously given by Guoli Ding in [Subgraphs and well-quasi-ordering, Journal of Graph Theory, 16(5):489–502, 1992] for subgraphs and Peter Damaschke in [Induced subgraphs and well-quasi-ordering, Journal of Graph Theory, 14(4):427–435, 1990] for induced subgraphs.
Type de document :
Communication dans un congrès
The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015, Aug 2015, Bergen, Norway. 49, pp.197-201, 2015, 〈10.1016/j.endm.2015.06.029〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01349277
Contributeur : Isabelle Gouat <>
Soumis le : mercredi 27 juillet 2016 - 09:35:04
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Fichier

endm1907.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Jarosław Błasiok, Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck. Induced minors and well-quasi-ordering. The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015, Aug 2015, Bergen, Norway. 49, pp.197-201, 2015, 〈10.1016/j.endm.2015.06.029〉. 〈lirmm-01349277〉

Partager

Métriques

Consultations de la notice

199

Téléchargements de fichiers

163