Decomposing oriented graphs into transitive tournaments
type: Item
instance of: scholarly article
title: Decomposing oriented graphs into transitive tournaments
zbMATH Open document ID: 1086.05036
author: Raphael Yuster
published in: Discrete Mathematics
publication date: 2006-03-20T00:00:00Z
review text: If \(G\) is an oriented graph with \(n\) vertices, let \(f(G)\) denote the least number of arc-disjoint transitive subtournaments whose union includes all arcs of \(G\). The author shows that, in general, \(f(G)\leq\lfloor n^2/3\rfloor\) and that equality holds when \(G\) has at most \(n^2/3\) arcs. He also shows, among other things, that if \(G\) is a tournament, then \((n^2/3000)(1+ o(1))< f(G)< (5n^2/21)(1+ o(1))\).
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5013289
zbMATH Keywords: decomposition
reviewed by: J. W. Moon
MaRDI profile type: Publication
full work available at URL: j.disc.2005.11.008
OpenAlex ID: W1989274827
cites work: Q3852212
cites work: Q4873725
cites work: The Representation of a Graph by Set Intersections
cites work: Q5509547
cites work: Near perfect coverings in graphs and hypergraphs
cites work: Mathematical Foundations of Computer Science 2004
cites work: Disproof of a conjecture of Erdös and moser on tournaments
cites work: Q4083463
cites work: The number of edge-disjoint transitive triples in a tournament
DOI: 10.1016/J.DISC.2005.11.008
description: scientific article; zbMATH DE number 5013289