Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
digraph; minor; contraction
digraph; minor; contraction
Summary:
We show that any digraph on $n\ge3$ vertices and with not less than $3n-3$ arcs is contractible onto ${}^*\!K_3$.
References:
[1] Bollobas B., Catlin P. A., Erdös P.: Hadwiger's conjecture is true for almost every graph. European J. Combin. 1 (1980), 195-199. DOI 10.1016/S0195-6698(80)80001-1 | MR 0593989 | Zbl 0457.05041
[2] Dirac G. A.: A property of 4-chromatic graphs and some remarks on critical graphs. J. London Math. Soc. 27 (1952), 85-92. DOI 10.1112/jlms/s1-27.1.85 | MR 0045371 | Zbl 0046.41001
[3] Duchet P., Kaneti V.: Sur la contractibilité d'un graphe orienté en $*K_4$. Discrete Math. 130 (1994), 57-68. MR 1284749
[4] Hadwiger H.: Über eine Klassifikation der Streckenkcomplexe. Vierteljschr. Naturforsch. Ges. Zürich 88 (1943), 133-142. MR 0012237
[5] Jacob H., Meyniel H.: Extensions of Turan's and Brooks theorem and new notions of stability and colouring in digraphs. Ann. Discrete Math. 17 (1983), 365-370.
[6] Jagger C.: An extremal function for digraph subcontraction. J. Graph. Theory 21 (1996), 343-350. DOI 10.1002/(SICI)1097-0118(199603)21:3<343::AID-JGT10>3.0.CO;2-I | MR 1374908 | Zbl 0844.05046
[7] Kostochka A. V.: Lower bound on the Hadwiger number of graph by their average degree. Combinatorica 4 (1984), 307-316. DOI 10.1007/BF02579141 | MR 0779891
[8] Meyniel H.: Contractibilité de graphes orienté on $*K_3$. Private communication.
[9] Robertson N., Seymour P., Thomas R.: Hadviger's conjecture for $K_6$-free graphs. Combinatorica 13 (1993), 279-361. DOI 10.1007/BF01202354 | MR 1238823
[10] Thomason A.: An extremal function for contractions of graphs. Math. Proc. Combridge Philos. Soc. 95 (1984), 261-265. DOI 10.1017/S0305004100061521 | MR 0735367 | Zbl 0551.05047
[11] Wagner K.: Bemerkungen zu Hadwigers Vermutung. Math. Ann. 141 (1960), 433-451. DOI 10.1007/BF01360256 | MR 0121309 | Zbl 0096.17904
Search
Partner of
