Portal de Periódicos da CAPES

Induced minors and well-quasi-ordering

2018; Elsevier BV; Volume: 134; Linguagem: Inglês

10.1016/j.jctb.2018.05.005

1096-0902

Jarosław Błasiok, Marcin Kamiński, Jean‐Florent Raymond, Théophile Trunck,

Limits and Structures in Graph Theory

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 that K4-induced minor-free graphs are well-quasi-ordered by induced minors (Robin Thomas, 1985, [24]). 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 induced minors 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. To this end we prove two decomposition theorems which are of independent interest. Similar dichotomy results were previously given for subgraphs by Guoli Ding (1992) [5] and for induced subgraphs by Peter Damaschke (1990) [4].