Digraphs contractible onto * K 3

Stefan Janaqi; François Lescure; M. Maamoun; Henry Meyniel

Mathematica Bohemica (1998)

  • Volume: 123, Issue: 4, page 365-369
  • ISSN: 0862-7959

Abstract

top
We show that any digraph on n ≥ 3 vertices and with not less than 3 n - 3 arcs is contractible onto * K 3 .

How to cite

top

Janaqi, Stefan, et al. "Digraphs contractible onto $^*K_3$." Mathematica Bohemica 123.4 (1998): 365-369. <http://eudml.org/doc/248304>.

@article{Janaqi1998,
abstract = {We show that any digraph on $n\ge 3$ vertices and with not less than $3n-3$ arcs is contractible onto $\{\}^*\!K_3$.},
author = {Janaqi, Stefan, Lescure, François, Maamoun, M., Meyniel, Henry},
journal = {Mathematica Bohemica},
keywords = {digraph; minor; contraction; digraph; minor; contraction},
language = {eng},
number = {4},
pages = {365-369},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Digraphs contractible onto $^*K_3$},
url = {http://eudml.org/doc/248304},
volume = {123},
year = {1998},
}

TY - JOUR
AU - Janaqi, Stefan
AU - Lescure, François
AU - Maamoun, M.
AU - Meyniel, Henry
TI - Digraphs contractible onto $^*K_3$
JO - Mathematica Bohemica
PY - 1998
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 123
IS - 4
SP - 365
EP - 369
AB - We show that any digraph on $n\ge 3$ vertices and with not less than $3n-3$ arcs is contractible onto ${}^*\!K_3$.
LA - eng
KW - digraph; minor; contraction; digraph; minor; contraction
UR - http://eudml.org/doc/248304
ER -

References

top
  1. Bollobas B., Catlin P. A., Erdös P., 10.1016/S0195-6698(80)80001-1, European J. Combin. 1 (1980), 195-199. (1980) Zbl0457.05041MR0593989DOI10.1016/S0195-6698(80)80001-1
  2. Dirac G. A., 10.1112/jlms/s1-27.1.85, J. London Math. Soc. 27 (1952), 85-92. (1952) Zbl0046.41001MR0045371DOI10.1112/jlms/s1-27.1.85
  3. Duchet P., Kaneti V., Sur la contractibilité d’un graphe orienté en * K 4 , Discrete Math. 130 (1994), 57-68. (1994) MR1284749
  4. Hadwiger H., Über eine Klassifikation der Streckenkcomplexe, Vierteljschr. Naturforsch. Ges. Zürich 88 (1943), 133-142. (1943) MR0012237
  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. (1983) 
  6. Jagger C., 10.1002/(SICI)1097-0118(199603)21:3<343::AID-JGT10>3.0.CO;2-I, J. Graph. Theory 21 (1996), 343-350. (1996) Zbl0844.05046MR1374908DOI10.1002/(SICI)1097-0118(199603)21:3<343::AID-JGT10>3.0.CO;2-I
  7. Kostochka A. V., 10.1007/BF02579141, Combinatorica 4 (1984), 307-316. (1984) MR0779891DOI10.1007/BF02579141
  8. Meyniel H., Contractibilité de graphes orienté on * K 3 , Private communication. 
  9. Robertson N., Seymour P., Thomas R., 10.1007/BF01202354, Combinatorica 13 (1993), 279-361. (1993) MR1238823DOI10.1007/BF01202354
  10. Thomason A., 10.1017/S0305004100061521, Math. Proc. Combridge Philos. Soc. 95 (1984), 261-265. (1984) Zbl0551.05047MR0735367DOI10.1017/S0305004100061521
  11. Wagner K., 10.1007/BF01360256, Math. Ann. 141 (1960), 433-451. (1960) Zbl0096.17904MR0121309DOI10.1007/BF01360256

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.