Transitive tournament tilings in oriented graphs with large minimum total degree

DOI10.1137/19M1269257MaRDI QIDQ5854457zbMATH OpenOpenAlexFDO

Authors Louis DeBiasio, Allan Lo, Theodore Molla, Andrew Treglown

Publication date 17 March 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.07648

zbMATH Keywords

absorbingfractional matchinglinear programmingoriented Ramseytiling Ramseytournaments

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Fractional graph theory, fuzzy graph theory (05C72) Ramsey theory (05D10) Linear programming (90C05)

Abstract: Let $vec{T}_k$ be the transitive tournament on $k$ vertices. We show that every oriented graph on $n=4m$ vertices with minimum total degree $(11/12+o(1))n$ can be partitioned into vertex disjoint $vec{T}_4$'s, and this bound is asymptotically tight. We also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint $vec{T}_k$'s.

Recommendations

• Tiling transitive tournaments and their blow-ups
• Transitive triangle tilings in oriented graphs
• Decomposing oriented graphs into transitive tournaments
• Subdivisions of digraphs in tournaments
• Tiling directed graphs with tournaments

Cites work

• \(F\)-factors in hypergraphs via absorption
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A note on some embedding problems for oriented graphs
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• Combinatorial and computational aspects of graph packing and graph decomposition
• Cyclic triangle factors in regular tournaments
• Decomposition of large combinatorial structures
• scientific article; zbMATH DE number 568832 (Why is no real title available?)
• scientific article; zbMATH DE number 3221981 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Independent directed triangles in a directed graph
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• On directed versions of the Hajnal-Szemerédi theorem
• On tournaments free of large transitive subtournaments
• Practical graph isomorphism. II.
• Tiling directed graphs with tournaments
• Tiling transitive tournaments and their blow-ups
• Transitive triangle tilings in oriented graphs
• Triangle packings and 1-factors in oriented graphs

Cited in

(6)

• The interchange graphs of tournaments with minimum score vectors are exactly hypercubes
• Tiling transitive tournaments and their blow-ups
• Transitive triangle tilings in oriented graphs
• Tiling directed graphs with tournaments
• A note between transitive C₄-factor and oriented Ramsey number
• TT₃-factors in oriented graphs with low independence number

Describes a project that uses

Uses Software

• nauty
• Traces

This page was built for publication: Transitive tournament tilings in oriented graphs with large minimum total degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5854457)