Subdivisions of Transitive Tournaments
✍
A.D. Scott
📂
Article
📅
2000
🏛
Elsevier Science
🌐
English
⚖ 77 KB
We prove that, for r ≥ 2 and n ≥ n(r ), every directed graph with n vertices and more edges than the r -partite Turán graph T (r, n) contains a subdivision of the transitive tournament on r + 1 vertices. Furthermore, the extremal graphs are the orientations of T (r, n) induced by orderings of the ve