✦ LIBER ✦

On some minimal graphs of the torus

✍ Scribed by R. Bodendiek; K. Wagner

Publisher: John Wiley and Sons
Year: 1985
Tongue: English
Weight: 259 KB
Volume: 9
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190090312

No coin nor oath required. For personal study only.

✦ Synopsis

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 subgraph W.

📜 SIMILAR VOLUMES

Grid Minors of Graphs on the Torus

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

Graphs on the Torus and Geometry of Numb

Graphs on the Torus and Geometry of Numbers

✍ A. Schrijver 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 424 KB

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

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

On the minimum degree of minimal Ramsey

On the minimum degree of minimal Ramsey graphs

✍ Tibor Szabó; Philipp Zumstein; Stefanie Zürcher 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 1 views

## Abstract We investigate the minimization problem of the minimum degree of minimal Ramsey graphs, initiated by Burr et al. We determine the corresponding graph parameter for numerous bipartite graphs, including bi‐regular bipartite graphs and forests. We also make initial progress for graphs of l

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

The minimum degree of Ramsey-minimal gra

The minimum degree of Ramsey-minimal graphs

✍ Jacob Fox; Kathy Lin 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

## Abstract We write __H__ → __G__ if every 2‐coloring of the edges of graph __H__ contains a monochromatic copy of graph __G__. A graph __H__ is __G__‐__minimal__ if __H__ → __G__, but for every proper subgraph __H__′ of __H__, __H__′ ↛ __G__. We define __s__(__G__) to be the minimum __s__ such th