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

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

Research output: Contribution to journalArticle

2 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 languageEnglish (US)
Pages (from-to)40-45
Number of pages6
JournalJournal of Combinatorial Theory, Series B
Volume58
Issue number1
DOIs
StatePublished - May 1993

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Disjoint Cycles in Directed Graphs on the Torus and the Klein Bottle'. Together they form a unique fingerprint.

  • Cite this