Monochromatic directed walks in arc-colored directed graphs (Q1088681): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Noga Alon / rank | |||
Property / author | |||
Property / author: Noga Alon / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Monochromatic paths and circuits in edge-colored graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Monochromatic paths in edge-colored graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A decomposition theorem for partially ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nombre chromatique et plus longs chemins d'un graphe / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf01956320 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1994009802 / rank | |||
Normal rank |
Latest revision as of 10:51, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Monochromatic directed walks in arc-colored directed graphs |
scientific article |
Statements
Monochromatic directed walks in arc-colored directed graphs (English)
0 references
1987
0 references
\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. \]
0 references
directed graph
0 references
directed path
0 references
monochromatic walk
0 references
monochromatic directed walk
0 references