Grids and their minors
type: Item
instance of: scholarly article
title: Grids and their minors
zbMATH Open document ID: 0636.05023
DOI: 10.1016/0095-8956(89)90033-6
published in: Journal of Combinatorial Theory. Series B
publication date: 1989-01-01T00:00:00Z
review text: We define graphs \(Y_ n\) such that none of these \(Y_ n\) has a minor isomorphic to \(K_ 8\) and for every number k and surface S not all of these graphs are in the completion of k-vertex extensions of graphs embeddable in S. This disproves a corresponding conjecture of \textit{N. Robertson} and \textit{P. D. Seymour} [Graph width and well-quasi-ordering: a survey, Progress in Graph Theory, Proc. Conf. Combinatorics, Waterloo/Ont. 1982, 399-406 (1984; Zbl 0566.05052)].
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 4035859
zbMATH Keywords: graphs
zbMATH Keywords: minor
zbMATH Keywords: surface
author: Detlef Seese
author: Walter Wessel
MaRDI profile type: Publication
full work available at URL: 0095-8956(89)90033-6
OpenAlex ID: W2070637453
cites work: Q3856672
cites work: Q5620616
cites work: Q5572939
cites work: Q3887500
cites work: SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
cites work: Graph minors. I. Excluding a forest
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Graph minors. III. Planar tree-width
cites work: Graph minors. IV: Tree-width and well-quasi-ordering
cites work: Graph minors. V. Excluding a planar graph
cites work: Graph minors. VI. Disjoint paths across a disc
cites work: Graph minors. VII: Disjoint paths on a surface
cites work: Graph minors. VIII: A Kuratowski theorem for general surfaces
cites work: Q3222217
cites work: Q3680875
cites work: A combinatorial and logical approach to linear-time computability (extended abstract)
cites work: Q3692864
cites work: Q3880860
cites work: Graph minors. IX: Disjoint crossed paths
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Graph minors. XI: Circuits on a surface
cites work: Graph minors. XVI: Excluding a non-planar graph
description: scientific article; zbMATH DE number 4035859