Geodesic
Digraphs contractible onto $\sp *K\sb 3$
Mathematica Bohemica, Tome 123 (1998) no. 4, pp. 365-369

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
We show that any digraph on $n\ge3$ vertices and with not less than $3n-3$ arcs is contractible onto ${}^*\!K_3$.
We show that any digraph on $n\ge3$ vertices and with not less than $3n-3$ arcs is contractible onto ${}^*\!K_3$.
DOI : 10.21136/MB.1998.125971
Classification : 05C20
Keywords: digraph; minor; contraction 
Janaqi, Stefan; Lescure, F.; Maamoun, M.; Meyniel, H. Digraphs contractible onto $\sp *K\sb 3$. Mathematica Bohemica, Tome 123 (1998) no. 4, pp. 365-369. doi: 10.21136/MB.1998.125971
@article{10_21136_MB_1998_125971,
     author = {Janaqi, Stefan and Lescure, F. and Maamoun, M. and Meyniel, H.},
     title = {Digraphs contractible onto $\sp *K\sb 3$},
     journal = {Mathematica Bohemica},
     pages = {365--369},
     year = {1998},
     volume = {123},
     number = {4},
     doi = {10.21136/MB.1998.125971},
     mrnumber = {1667109},
     zbl = {0934.05069},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.1998.125971/}
}
TY  - JOUR
AU  - Janaqi, Stefan
AU  - Lescure, F.
AU  - Maamoun, M.
AU  - Meyniel, H.
TI  - Digraphs contractible onto $\sp *K\sb 3$
JO  - Mathematica Bohemica
PY  - 1998
SP  - 365
EP  - 369
VL  - 123
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.1998.125971/
DO  - 10.21136/MB.1998.125971
LA  - en
ID  - 10_21136_MB_1998_125971
ER  - 
%0 Journal Article
%A Janaqi, Stefan
%A Lescure, F.
%A Maamoun, M.
%A Meyniel, H.
%T Digraphs contractible onto $\sp *K\sb 3$
%J Mathematica Bohemica
%D 1998
%P 365-369
%V 123
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.1998.125971/
%R 10.21136/MB.1998.125971
%G en
%F 10_21136_MB_1998_125971

[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 | MR | Zbl

[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 | MR | Zbl

[3] Duchet P., Kaneti V.: Sur la contractibilité d'un graphe orienté en $*K_4$. Discrete Math. 130 (1994), 57-68. | MR

[4] Hadwiger H.: Über eine Klassifikation der Streckenkcomplexe. Vierteljschr. Naturforsch. Ges. Zürich 88 (1943), 133-142. | MR

[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 | MR | Zbl

[7] Kostochka A. V.: Lower bound on the Hadwiger number of graph by their average degree. Combinatorica 4 (1984), 307-316. | DOI | MR

[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 | MR

[10] Thomason A.: An extremal function for contractions of graphs. Math. Proc. Combridge Philos. Soc. 95 (1984), 261-265. | DOI | MR | Zbl

[11] Wagner K.: Bemerkungen zu Hadwigers Vermutung. Math. Ann. 141 (1960), 433-451. | DOI | MR | Zbl

Cité par Sources :