| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Induced minors and well-quasi-ordering | Jarosław Błasiok
; Marcin Kamiński
; Jean-Florent Raymond
; Théophile Trunck
; | Date: |
24 Oct 2015 | 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 that $K_4$-induced minor-free
graphs are well-quasi-ordered by induced minors [Graphs without $K_4$ and
well-quasi-ordering, Journal of Combinatorial Theory, Series B, 38(3):240 --
247, 1985].
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. To this end we proved
two decomposition theorems which are of independent interest.
Similar dichotomy results were previously given for subgraphs by Guoli Ding
in [Subgraphs and well-quasi-ordering, Journal of Graph Theory, 16(5):489--502,
1992] and for induced subgraphs by Peter Damaschke in [Induced subgraphs and
well-quasi-ordering, Journal of Graph Theory, 14(4):427--435, 1990]. | Source: | arXiv, 1510.7135 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |