Cycles in Unions of Transitive Tournaments
At a glance
- الاستشهادات
- 0
- المراجع
- 0
- Comments
- 0
Abstract
A tournament is an orientation of a complete graph. A bitournament is an orientation of a complete bipartite graph. Let G be an oriented graph which is the (not necessarily disjoint) union of a bounded number of transitive tournaments. When is it possible to remove the arc sets of a bounded number of transitive bitournaments from G in order to make G acyclic? In this paper, we begin investigating this question and its ties to lettericity of graphs and geometric griddability of permutations, two independently developed notions that highlight very similar structural features in their respective objects. We explore the problem through the lens of "minimal obstructions", i.e. minimal classes of directed graphs for which this is not possible, and identify an infinite collection of such classes.
Publication details
- DOI
- 10.4230/lipics.wg.2026.3
- OpenAlex
- W4403347100
- Document type
- preprint
- Language
- EN
- Source
- arXiv (Cornell University)
- Last metadata update
Comments
تسجيل الدخول للانضمام إلى النقاش.