Antidirected paths in 5-chromatic digraphs

Amine El Sahili

doi:10.1016/j.crma.2004.06.028

Logic

Antidirected paths in 5-chromatic digraphs

Presented by: Jean-Yves Girard

Amine El Sahili ¹

¹ Section I, Sciences Faculty, Lebanese University, Beyrouth, Lebanon

Comptes Rendus. Mathématique, Volume 339 (2004) no. 5, pp. 317-320.

Abstract
Résumé

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

Soit $T_{5}$ le tournoi régulier contenant cinq sommets. B. Grünbaum a prouvé que $T_{5}$ est le seul 5-tournoi qui ne contient pas le chemin antidirigé $P_{4}$ . Nous prouvons dans cette Note que $T_{5}$ 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é $P_{4}$ . On prouve à l'aide d'un exemple que la condition « tout sommet a un degré exterieur au moins deux » est indispensable.

Received: 2004-06-16
Accepted: 2004-06-22
Published online: 2004-08-14

DOI: 10.1016/j.crma.2004.06.028

Author's affiliations:

Amine El Sahili ¹

¹ 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/

References
Cited by

[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

Cited by Sources:

Comments - Policy