DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.3

Cycles in Unions of Transitive Tournaments

Authors: Bogdan Alecu, Pedro Bureo Villafana, and Vadim Lozin

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

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.

Cite as

Bogdan Alecu, Pedro Bureo Villafana, and Vadim Lozin. Cycles in Unions of Transitive Tournaments. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alecu_et_al:LIPIcs.WG.2026.3,
  author =	{Alecu, Bogdan and Bureo Villafana, Pedro and Lozin, Vadim},
  title =	{{Cycles in Unions of Transitive Tournaments}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.3},
  URN =		{urn:nbn:de:0030-drops-261694},
  doi =		{10.4230/LIPIcs.WG.2026.3},
  annote =	{Keywords: Structural graph theory, directed graphs, permutation patterns, graph lettericity, minimum feedback arc set problem, well-quasi-orderability, transitive tournaments}
}

Search Results

Documents authored by Alecu, Bogdan

Cycles in Unions of Transitive Tournaments

Abstract

Cite as

Thanks for your feedback!

Could not send message