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

Présenté par : Jean-Yves Girard

El Sahili, Amine1
1 Section I, Sciences Faculty, Lebanese University, Beyrouth, Lebanon
Comptes Rendus. Mathématique, Tome 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
El Sahili, Amine 1

1 Section I, Sciences Faculty, Lebanese University, Beyrouth, Lebanon 
@article{CRMATH_2004__339_5_317_0,
     author = {El Sahili, Amine},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2004.06.028/}
}
TY  - JOUR
AU  - El Sahili, Amine
TI  - Antidirected paths in 5-chromatic digraphs
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 317
EP  - 320
VL  - 339
IS  - 5
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2004.06.028/
DO  - 10.1016/j.crma.2004.06.028
LA  - en
ID  - CRMATH_2004__339_5_317_0
ER  - 
%0 Journal Article
%A El Sahili, Amine
%T Antidirected paths in 5-chromatic digraphs
%J Comptes Rendus. Mathématique
%D 2004
%P 317-320
%V 339
%N 5
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2004.06.028/
%R 10.1016/j.crma.2004.06.028
%G en
%F CRMATH_2004__339_5_317_0
El Sahili, Amine. Antidirected paths in 5-chromatic digraphs. Comptes Rendus. Mathématique, Tome 339 (2004) no. 5, pp. 317-320. doi : 10.1016/j.crma.2004.06.028. http://www.numdam.org/articles/10.1016/j.crma.2004.06.028/

[1] El Sahili, A. 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] Gallai, T. Kritische Graphen, I, Publ. Math. Inst. Hangar. Acad. Sci., Volume 8 (1963), pp. 165-192

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

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

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

[7] Roy, B. 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 :