Monochromatic directed walks in arc-colored directed graphs
type: Item
instance of: scholarly article
title: Monochromatic directed walks in arc-colored directed graphs
zbMATH Open document ID: 0613.05032
DOI: 10.1007/BF01956320
published in: Acta Mathematica Hungarica
publication date: 1987-01-01T00:00:00Z
review text: \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. \]
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 3991538
zbMATH Keywords: directed graph
zbMATH Keywords: directed path
zbMATH Keywords: monochromatic walk
zbMATH Keywords: monochromatic directed walk
author: Noga Alon
MaRDI profile type: Publication
cites work: Monochromatic paths and circuits in edge-colored graphs
cites work: Monochromatic paths in edge-colored graphs
cites work: A decomposition theorem for partially ordered sets
cites work: Q4198056
cites work: Nombre chromatique et plus longs chemins d'un graphe
full work available at URL: https://doi.org/10.1007/bf01956320
OpenAlex ID: W1994009802
description: scientific article; zbMATH DE number 3991538