Sur la contractibilité d'un graphe orien
✍
Pierre Duchet; Viktor Kaneti
📂
Article
📅
1994
🏛
Elsevier Science
🌐
English
⚖ 853 KB
We prove that every directed graph with n vertices and at least k-8 arcs admits the complete symmetric digraph of order 4 as a minor. The result is sharp. This answers a question raised by Meyniel (1983). We conclude with some open problems.