Comptes Rendus
no. 5
Logic
Antidirected paths in 5-chromatic digraphs
[Chemins antidirigés dans les graphes 5-chromatiques.]

Présenté par : Jean-Yves Girard

Amine El Sahili1
1 Section I, Sciences Faculty, Lebanese University, Beyrouth, Lebanon
Comptes Rendus. Mathématique, Volume 339 (2004) no. 5, pp. 317-320.

Soit T5 le tournoi régulier contenant cinq sommets. B. Grünbaum a prouvé que T5 est le seul 5-tournoi qui ne contient pas le chemin antidirigé P4. Nous prouvons dans cette Note que T5 est le seul graphe orienté 5-chromatique dans lequel tout sommet a un degré extérieur au moins deux qui ne contient pas le chemin antidirigé P4. On prouve à l'aide d'un exemple que la condition « tout sommet a un degré exterieur au moins deux » est indispensable.

Let T5 be the regular 5-tournament. B. Grünbaum proved that T5 is the only 5-tournament which contains no copy of the antidirected path P4. In this Note, we prove that, except for T5, any connected 5-chromatic oriented digraph in which each vertex has out-degree at least two contains a copy of P4. It will be shown, by an example, that the condition that each vertex has out-degree at least two is indispensable.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2004.06.028
Amine El Sahili 1

1 Section I, Sciences Faculty, Lebanese University, Beyrouth, Lebanon 
@article{CRMATH_2004__339_5_317_0,
     author = {Amine El Sahili},
     title = {Antidirected paths in 5-chromatic digraphs},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {317--320},
     publisher = {Elsevier},
     volume = {339},
     number = {5},
     year = {2004},
     doi = {10.1016/j.crma.2004.06.028},
     language = {en},
}
TY  - JOUR
AU  - Amine El Sahili
TI  - Antidirected paths in 5-chromatic digraphs
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 317
EP  - 320
VL  - 339
IS  - 5
PB  - Elsevier
DO  - 10.1016/j.crma.2004.06.028
LA  - en
ID  - CRMATH_2004__339_5_317_0
ER  - 
%0 Journal Article
%A Amine El Sahili
%T Antidirected paths in 5-chromatic digraphs
%J Comptes Rendus. Mathématique
%D 2004
%P 317-320
%V 339
%N 5
%I Elsevier
%R 10.1016/j.crma.2004.06.028
%G en
%F CRMATH_2004__339_5_317_0
Amine El Sahili. Antidirected paths in 5-chromatic digraphs. Comptes Rendus. Mathématique, Volume 339 (2004) no. 5, pp. 317-320. doi : 10.1016/j.crma.2004.06.028. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2004.06.028/

[1] A. El Sahili Functions and line digraphs, J. Graph Theory, Volume 4 (2003), pp. 296-303

[2] A. El Sahili, Paths with two blocks in k-chromatic digraphs, J. Discrete Math., in press

[3] T. Gallai Kritische Graphen, I, Publ. Math. Inst. Hangar. Acad. Sci., Volume 8 (1963), pp. 165-192

[4] T. Gallai On directed paths and circuits (P. Erdös; G. Katona, eds.), Theory of Graphs, Academic Press, 1968, pp. 115-118

[5] B. Grünbaum Antidirected Hamiltonian paths in tournaments, J. Comb. Theory B, Volume 11 (1971), pp. 469-474

[6] F. Havet; S. Thomassé Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld's conjecture, J. Comb. Theory B, Volume 78 (2000) no. 2, pp. 243-273

[7] B. Roy Nombre chromatique et plus longs chemins d'un graphe, Rev. Française Automat. Informat. Recherche Opérationelle Sér. Rouge, Volume 1 (1967), pp. 127-132

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Claws in digraphs

Amine El Sahili; Mekkia Kouider

C. R. Math (2008)

The (⩽6)-half-reconstructibility of digraphs

Jamel Dammak; Baraa Salem

C. R. Math (2014)

Graph-theoretical methods in general function theory

Amine El Sahili

C. R. Math (2002)