Monochromatic directed walks in arc-colored directed graphs (Q1088681): Difference between revisions

\textit{T. Gallai} [Theory of graphs, Proc. Colloquium Tihany, Hungary 1966, 115-118 (1968; Zbl 0159.544)] and \textit{B. Roy} [Revue Franc. Inform. Rech. operat. 1, 129-132 (1967; Zbl 0157.313)] independently showed that every directed graph D contains a directed path of length \(\chi\) (D)-1. \textit{V. Chvátal} [J. Comb. Theory, Ser. B 13, 69-70 (1972; Zbl 0221.05064)] observed that the result of Gallai and Roy implies the following: Let D be any directed graph and let k and r be positive integers such that \(\chi (D)>k^ r\); then in any arc-coloring of D with r colors, D contains a monochromatic path (and hence a monochromatic walk) of length k. In this paper the following definitions are made: (1) An arc-coloring of a directed graph d is k-free (k\(\geq 2)\) if D does not contain a monochromatic directed walk of length k. (2) \(C_ k(D)=\min \{r:\) there exists a \(k\)-free arc-coloring of \(D\) with \(r\) colors\(\}\). (3) \(\underline C_ k(h) = \min \{C_ k(D):\) D is a directed graph and \(\chi (D)=h\}\), \(h,k\geq 2.\) (4) \(\bar C_ k(h) = \max \{C_ k(D):\) D is a directed graph and \(\chi (D)=h\}\), \(h,k\geq 2.\) Among other results, it is shown that, for all \(h,k\geq 2\), \[ \lceil \log_ kh\rceil =\underline C_ k(h)\leq \bar C_ k(h)\leq \lceil \log_ kh+\log_ k\log_ kh+4\rceil. \]