preprint وصول مفتوح

Cycles in Unions of Transitive Tournaments

  • arXiv (Cornell University)
  • Cornell University
Research footprint

At a glance

الاستشهادات
0
المراجع
0
Comments
0
Paper overview

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.

Record transparency

Publication details

DOI
10.4230/lipics.wg.2026.3
OpenAlex
W4403347100
Document type
preprint
Language
EN
Source
arXiv (Cornell University)
Last metadata update
المجتمع

Comments

تسجيل الدخول للانضمام إلى النقاش.

  1. لا توجد تعليقات بعد. ابدأ النقاش.