Immersion of transitive tournaments in digraphs with large minimum outdegree

2017/10/31 by Lochet, W.
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1710.11482

Abstract

We prove the existence of a function h(k) such that every simple digraph with minimum outdegree greater than h(k) contains an immersion of the transitive tournament on k vertices. This solves a conjecture of Devos, McDonald, Mohar and Scheide.

Related

• Immersions of directed graphs in tournaments
• A note on complete subdivisions in digraphs of large outdegree
• Immersing complete digraphs
• Subdivisions of digraphs in tournaments
• Strong immersion is a well-quasi-ordering for semi-complete digraphs