On restricted colourings of Kn

Simonovits, Miklós and T. Sós, Vera (1984) On restricted colourings of Kn. COMBINATORICA, 4 (1). pp. 101-110. ISSN 0209-9683

Preview

Text Simonovits-Sos1984_Article_OnRestrictedColouringsOfKn.pdf Download (484kB) | Preview

Abstract

The authors investigate Ramsey-type extremal problems for finite graphs. In Section 1, anti-Ramsey numbers for paths are determined. For positive integers k and n let r=f(n,Pk) be the maximal integer such that there exists an edge colouring of Kn using precisely r colours but not containing any coloured path on k vertices with all edges having different colors. It is shown that f(n,P2k+3+ε)=t⋅n−(t+12)+1+ε for t≥5, n>c⋅t2 and ε=0,1. In Section 2, K3-spectra of colourings are determined. Given S⊆{1,2,3}, the authors investigate for which r and n there exist edge colourings of Kn using precisely r colours such that all triangles are s-coloured for some s∈S and, conversely, every s∈S occurs. Section 3 contains suggestions for further research.

Actions (login required)

Edit Item