zbMATH — the first resource for mathematics

About paths with two blocks. (English) Zbl 1121.05065
Summary: The function \(f(n)\) is defined to be the smallest integer such that any \(f(n)\)-chromatic digraph contains all paths with two blocks \(P(k,j)\) with \(k + j = n - 1\). A. El Sahili [Discrete Math. 287, No. 1–3, 151–153 (2004; Zbl 1050.05072)] conjectured that \(f(n) = n\). We prove in this paper that \(f(n) \leq n + 1\). Our argument yields a very short and direct proof of the Gallai-Roy result about directed paths. We also treat the problem under some supplementary conditions. One of them is used to give a simple proof of a result of M. Saks and V. T. Sós [Colloq. Math. Soc. János Bolyai 37, No. 2, 663–674 (1984; Zbl 0566.05032)] about claws.

05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Subtrees of directed graphs and hypergraphs, In Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla.), I, 28 (1980), pp. 227–239.
[2] A. El, Disc Math 287 pp 151– (2004)
[3] On directed paths and circuits, Theory of Graphs, and (Editors), Academic press, New York, 1968, pp. 115–118.
[4] F., Graphs Combinat 19 pp 101– (2003)
[5] F., J Graph Theory 35 pp 244– (2000)
[6] F., J Combinat Theory Ser B 78 pp 243– (2000)
[7] B., Rev Française Automat Informat Recherche Opérationelle Sér Rouge 1 pp 127– (1967)
[8] M., Colloquia Mathematica Societatis János Bolyai 37 pp 663– (1981)
[9] A., Trans Amer Math Soc 296 pp 167– (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.