Immersion of transitive tournaments in digraphs with large minimum outdegree

DOI10.1016/J.JCTB.2018.05.004MaRDI QIDQ1633763zbMATH OpenOpenAlexWikidataFDO

Authors William Lochet

Publication date 20 December 2018

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

digraphsimmersionstransitive tournaments

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07)

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.

Recommendations

• Immersing complete digraphs
• On the Erd\H{o}s-P\'osa property for immersions and topological minors in tournaments
• A note on complete subdivisions in digraphs of large outdegree
• On topological tournaments of order 4 in digraphs of outdegree 3
• A well-quasi-order for tournaments

Cites work

• A minimum degree condition forcing complete graph immersion
• Degree and local connectivity in digraphs
• Even cycles in directed graphs
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Immersing complete digraphs
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Topological cliques in graphs II

Cited in

(7)

• Immersion of complete digraphs in Eulerian digraphs
• Immersions of directed graphs in tournaments
• Immersing complete digraphs
• Isomorphism testing of k-spanning tournaments is fixed parameter tractable
• On the Erd\H{o}s-P\'osa property for immersions and topological minors in tournaments
• Subdivisions in dicritical digraphs with large order or digirth
• On digraphs without onion star immersions

This page was built for publication: Immersion of transitive tournaments in digraphs with large minimum outdegree

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