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

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: author (P16): Item:Q178698
RedirectionBot (talk | contribs)
Changed an Item
Property / author
 
Property / author: Noga Alon / rank
 
Normal rank

Revision as of 08:40, 10 February 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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references