| Title:
|
Digraphs contractible onto $\sp *K\sb 3$ (English) |
| Author:
|
Janaqi, Stefan |
| Author:
|
Lescure, F. |
| Author:
|
Maamoun, M. |
| Author:
|
Meyniel, H. |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
123 |
| Issue:
|
4 |
| Year:
|
1998 |
| Pages:
|
365-369 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
We show that any digraph on $n\ge3$ vertices and with not less than $3n-3$ arcs is contractible onto ${}^*\!K_3$. (English) |
| Keyword:
|
digraph |
| Keyword:
|
minor |
| Keyword:
|
contraction |
| MSC:
|
05C20 |
| idZBL:
|
Zbl 0934.05069 |
| idMR:
|
MR1667109 |
| DOI:
|
10.21136/MB.1998.125971 |
| . |
| Date available:
|
2009-09-24T21:33:08Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/125971 |
| . |
| Reference:
|
[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. Zbl 0457.05041, MR 0593989, 10.1016/S0195-6698(80)80001-1 |
| Reference:
|
[2] Dirac G. A.: A property of 4-chromatic graphs and some remarks on critical graphs.J. London Math. Soc. 27 (1952), 85-92. Zbl 0046.41001, MR 0045371, 10.1112/jlms/s1-27.1.85 |
| Reference:
|
[3] Duchet P., Kaneti V.: Sur la contractibilité d'un graphe orienté en $*K_4$.Discrete Math. 130 (1994), 57-68. MR 1284749 |
| Reference:
|
[4] Hadwiger H.: Über eine Klassifikation der Streckenkcomplexe.Vierteljschr. Naturforsch. Ges. Zürich 88 (1943), 133-142. MR 0012237 |
| Reference:
|
[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. |
| Reference:
|
[6] Jagger C.: An extremal function for digraph subcontraction.J. Graph. Theory 21 (1996), 343-350. Zbl 0844.05046, MR 1374908, 10.1002/(SICI)1097-0118(199603)21:3<343::AID-JGT10>3.0.CO;2-I |
| Reference:
|
[7] Kostochka A. V.: Lower bound on the Hadwiger number of graph by their average degree.Combinatorica 4 (1984), 307-316. MR 0779891, 10.1007/BF02579141 |
| Reference:
|
[8] Meyniel H.: Contractibilité de graphes orienté on $*K_3$.Private communication. |
| Reference:
|
[9] Robertson N., Seymour P., Thomas R.: Hadviger's conjecture for $K_6$-free graphs.Combinatorica 13 (1993), 279-361. MR 1238823, 10.1007/BF01202354 |
| Reference:
|
[10] Thomason A.: An extremal function for contractions of graphs.Math. Proc. Combridge Philos. Soc. 95 (1984), 261-265. Zbl 0551.05047, MR 0735367, 10.1017/S0305004100061521 |
| Reference:
|
[11] Wagner K.: Bemerkungen zu Hadwigers Vermutung.Math. Ann. 141 (1960), 433-451. Zbl 0096.17904, MR 0121309, 10.1007/BF01360256 |
| . |
