Canonical Ramsey numbers and properly colored cycles (Q1043941)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Canonical Ramsey numbers and properly colored cycles
scientific article

    Statements

    Canonical Ramsey numbers and properly colored cycles (English)
    0 references
    0 references
    10 December 2009
    0 references
    A cycle is called properly coloured if no two incident edges in it have the same colour. The first part of the paper contains and improvement of bounds on the so-called unordered Canonical Ramsey numbers. The the author proves a conjecture raised by \textit{M. Axenovich, T. Jiang} and \textit{Zs. Tuza} [Comb. Probab. Comput. 12, No. 5--6, 459--511 (2003; Zbl 1062.05096)] that for each \(k\geq 4\) and large \(n\), every edge-coloring of \(K_n\) in which at least \(256k\) different colours appear at each vertex contains a properly coloured cycle of length exactly \(k\). Moreover, the bound \(256k\) is tight up to a constant factor.
    0 references
    canonical Ramsey number
    0 references
    proper colouring
    0 references
    rainbow colouring
    0 references
    lexical colouring
    0 references
    colour degree
    0 references
    cycle
    0 references

    Identifiers