Logic
Antidirected paths in 5-chromatic digraphs
Comptes Rendus. Mathématique, Volume 339 (2004) no. 5, pp. 317-320.

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.

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.

Accepted:
Published online:
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

Cited by Sources:

Articles of potential interest

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)

${−1}$-self dual finite prechains and applications

Houcine Bouchaala; Youssef Boudabbous; Gérard Lopez

C. R. Math (2013)