Grid minors of graphs on the torus
type: Item
instance of: scholarly article
title: Grid minors of graphs on the torus
zbMATH Open document ID: 0809.05037
author: Maurits de Graaf
author: Alexander Schrijver
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-08-29T00:00:00Z
review text: The face-width of a graph embedded on the torus is the smallest \(n\) such that there is a noncontractible cycle on the torus which intersects the graph in exactly \(n\) points. For example, the product of two \(n\)-cycles \(C_ n\times C_ n\) embeds on the torus with face-width \(n\); this embedding is called the toroidal \(n\)-grid. A graph \(H\) is a minor of \(G\) if we can create \(H\) from \(G\) by a sequence of edge deletions and edge contractions. The authors show that any graph embedded on the torus with face-width \(r\geq 5\) contains the toroidal \(\lfloor 2r/3 \rfloor\)-grid as a minor. Moreover, the value \(\lfloor 2r/3\rfloor\) is the best possible. An equivalent form of the result is that every toroidal graph with face- width at least \(\lceil 3k/2\rceil\) contains a toroidal \(k\)-grid as a minor. The proof proceeds by taking an embedded toroidal graph and constructing an associated planar polygon with integer coordinates which is symmetric about the origin. The grid minor corresponds to the existence of two linearly independent integer vectors of a certain length.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 52B20
zbMATH DE Number: 599860
zbMATH Keywords: face-width
zbMATH Keywords: torus
zbMATH Keywords: noncontractible cycle
zbMATH Keywords: minor
zbMATH Keywords: toroidal graph
zbMATH Keywords: planar polygon
reviewed by: Dan S. Archdeacon
MaRDI profile type: Publication
full work available at URL: jctb.1994.1029
OpenAlex ID: W1970011611
DOI: 10.1006/JCTB.1994.1029
description: scientific article; zbMATH DE number 599860