Transitive tournament tilings in oriented graphs with large minimum total degree

Louis DeBiasio, Allan Lo, Theodore Molla, Andrew Treglown

Research output: Contribution to journalArticlepeer-review

104 Downloads (Pure)

Abstract

Let Tk 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 T4'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 T→k's.
Original languageEnglish
Pages (from-to)250–266
Number of pages17
JournalSIAM Journal on Discrete Mathematics
Volume35
Issue number1
DOIs
Publication statusPublished - 22 Feb 2021

Keywords

  • tournaments
  • linear programming
  • oriented ramsey
  • absorbing
  • fractional matching
  • tiling ramsey

Fingerprint

Dive into the research topics of 'Transitive tournament tilings in oriented graphs with large minimum total degree'. Together they form a unique fingerprint.

Cite this