✦ LIBER ✦

Graphs on the Torus and Geometry of Numbers

✍ Scribed by A. Schrijver

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 424 KB
Volume: 58
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1993.1033

No coin nor oath required. For personal study only.

✦ Synopsis

We show that if (G) is a graph embedded on the torus (S) and each nonnullhomotopic closed curve on (S) intersects (G) at least (r) times, then (G) contains at least (\left\lfloor\frac{3}{4} r\right\rfloor) pairwise disjoint nonnullhomotopic circuits. The factor (\frac{3}{4}) is best possible. We prove this by showing the equivalence of this bound to a bound in the two-dimensional geometry of numbers. To show the equivalence, we study integer norms, i.e., norms (|\cdot|) such that (|x|) is an integer for each integer vector (x). In particular, we show that each integer norm in two dimensions has associated with it a graph embedded on the torus, and conversely. 1993 Academic Press. Inc.

📜 SIMILAR VOLUMES

On some minimal graphs of the torus

✍ R. Bodendiek; K. Wagner 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 259 KB 👁 1 views

## Let be the set of finite, simple and nondirected graphs being not embeddable into the torus. Furthermore let >4 be a partial order-relation and M, (r) the minimal basis of I'. In this paper we determine three graphs of M, (r) being embeddable into the projective plane and containing the subgrap

Grid Minors of Graphs on the Torus

✍ M. Degraaf; A. Schrijver 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 197 KB

The bichromaticity of cylinder graphs an

The bichromaticity of cylinder graphs and torus graphs

✍ Dan Pritikin 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 420 KB

The bichromaticity of a bipartite graph B is defined as the maximum value of r + s for which B has the complete bipartite graph K,, as a homomorphic image We determine the bichromaticity of any bipartite cylinder graph C2,, x P, or torus graph CZn x C , , In the process, w e disprove a conjecture of

A note on the bichromatic numbers of gra

A note on the bichromatic numbers of graphs

✍ Dennis D. A. Epple; Jing Huang 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB 👁 2 views

Disjoint Cycles in Directed Graphs on th

Disjoint Cycles in Directed Graphs on the Torus and the Klein Bottle

✍ G.L. Ding; A. Schrijver; P.D. Seymour 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 203 KB

We give necessary and sufficient conditions for a directed graph embedded on the torus or the Klein bottle to contain pairwise disjoint circuits, each of a given orientation and homotopy, and in a given order. For the Klein bottle, the theorem is new. For the torus, the theorem was proved before by

On recognizing graphs by numbers of homo

On recognizing graphs by numbers of homomorphisms

✍ Zdeněk Dvořák 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

## Abstract Let hom (__G, H__) be the number of homomorphisms from a graph __G__ to a graph __H__. A well‐known result of Lovász states that the function hom (·, __H__) from all graphs uniquely determines the graph __H__ up to isomorphism. We study this function restricted to smaller classes of gra