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
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
0 references