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

Guoli Ding; A. Schrijver; P. D. Seymour

doi:10.1006/jctb.1993.1029

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

Guoli Ding, A. Schrijver, P. D. Seymour

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

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 P. D. Seymour. This paper gives a shorter proof of that result.

Original language	English (US)
Pages (from-to)	40-45
Number of pages	6
Journal	Journal of Combinatorial Theory, Series B
Volume	58
Issue number	1
DOIs	https://doi.org/10.1006/jctb.1993.1029
State	Published - May 1993
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1993.1029

Cite this

@article{2c6065844f5a4fe5b3eebc42835a6189,

title = "Disjoint Cycles in Directed Graphs on the Torus and the Klein Bottle",

abstract = "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 P. D. Seymour. This paper gives a shorter proof of that result.",

author = "Guoli Ding and A. Schrijver and Seymour, {P. D.}",

year = "1993",

month = may,

doi = "10.1006/jctb.1993.1029",

language = "English (US)",

volume = "58",

pages = "40--45",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

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

AU - Ding, Guoli

AU - Schrijver, A.

AU - Seymour, P. D.

PY - 1993/5

Y1 - 1993/5

N2 - 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 P. D. Seymour. This paper gives a shorter proof of that result.

AB - 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 P. D. Seymour. This paper gives a shorter proof of that result.

UR - http://www.scopus.com/inward/record.url?scp=44949267214&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=44949267214&partnerID=8YFLogxK

U2 - 10.1006/jctb.1993.1029

DO - 10.1006/jctb.1993.1029

M3 - Article

AN - SCOPUS:44949267214

SN - 0095-8956

VL - 58

SP - 40

EP - 45

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 1

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this