Let be the regular 5-tournament. B. Grünbaum proved that is the only 5-tournament which contains no copy of the antidirected path . In this Note, we prove that, except for , any connected 5-chromatic oriented digraph in which each vertex has out-degree at least two contains a copy of . It will be shown, by an example, that the condition that each vertex has out-degree at least two is indispensable.
Soit le tournoi régulier contenant cinq sommets. B. Grünbaum a prouvé que est le seul 5-tournoi qui ne contient pas le chemin antidirigé . Nous prouvons dans cette Note que 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é . On prouve à l'aide d'un exemple que la condition « tout sommet a un degré exterieur au moins deux » est indispensable.
Accepted:
Published online:
Amine El Sahili 1
@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}, }
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] 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] Kritische Graphen, I, Publ. Math. Inst. Hangar. Acad. Sci., Volume 8 (1963), pp. 165-192
[4] On directed paths and circuits (P. Erdös; G. Katona, eds.), Theory of Graphs, Academic Press, 1968, pp. 115-118
[5] Antidirected Hamiltonian paths in tournaments, J. Comb. Theory B, Volume 11 (1971), pp. 469-474
[6] Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld's conjecture, J. Comb. Theory B, Volume 78 (2000) no. 2, pp. 243-273
[7] 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