Excluding a long double path minor
type: Item
instance of: scholarly article
title: Excluding a long double path minor
zbMATH Open document ID: 0921.05054
author: Guoli Ding
published in: Journal of Combinatorial Theory. Series B
publication date: 1999-09-29T00:00:00Z
review text: The `height' of a graph \(G\) is defined to be the number of steps to construct \(G\) by two simple graph operations. Let \(B_n\) be the graph obtained from an \(n\)-edge path by doubling each edge in parallel. Then, for any minor-closed class \({\mathcal G}\) of graphs, the following are proved to be equivalent: (1) Some \(B_n\) is not in \({\mathcal G}\). (2) There is a number \(h\) such that every graph in \({\mathcal G}\) has height at most \(h\). (3) \({\mathcal G}\) is well-quasi-orderd by the topological minor relation. (4) There is a polynomial function \(p(\cdot)\) such that the number of paths of every graph \(G\) in \({\mathcal G}\) is at most \(p(| V(G)|+ | E(G)|)\).
reviewed by: Andreas Huck
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 839131
zbMATH Keywords: minor-closed class
zbMATH Keywords: minor
zbMATH Keywords: number of paths
MaRDI profile type: Publication
full work available at URL: jctb.1996.0002
OpenAlex ID: W2014605962
Wikidata QID: Q56235107
DOI: 10.1006/JCTB.1996.0002
description: scientific article; zbMATH DE number 839131