We show the existence of a constant c such that if n >I ck 3 and the edges of K,, are coloured using no colour more than k times then there is a Hamilton path with all edges of distinct colours. From this we infer that sr(Pn, k) = sr(Cn, k) = n, whenever n >t ck 3.
We follow for notation and terminology. Our graphs are simple andw except when notedwfinite. The sub-Ramsey number sr(G, k) of a graph G and a positive integer k is the least m such that in any edge-colouring of K,n using no colour more than k times there is a (subgraph isomorphic to) G whose edges all have distinct colours. The sub-Ramsey numbers exist and are bounded above by the generalized ramsey numbers r(G; k) (see ). The problem of determining sr(G, k) in general seems rather difficult although sr(G, k) = O(kn 3) for a graph G on n vertices . Here we_concentrate on sr(Pn, k) and sr(Cn, k), with Pn denoting a path on n vertices.
If Km is coloured so that at least two colours are used then, clearly, there is a 2-coloured P3. Furthermore, if at least three colours occur, it is easy to see that a 3-coloured P4 is present unless m ~<4. This implies that sr(P3, k)= [½(3 + V~ + 8k)J and if k > 2, then sr(Pa, k) = [½(3 + ~/1 + 16k)]. Note also that sr(P4, 2)= 5, by the preceding observation and the standard unique good colouring of K4.
An easy counting argument (if sr(P~, 2) > n, then in some edge-colouring of Kn using each colour at most twice each of the n[ ordered paths must contain a pair of edges of the same colour) shows that sr(Pn, 2) = n if n 1> 5. Our main result implies that sr(P~, k) = sr(Cn, k) = n for n large enough and k fixed.
In about 1978 the following conjectures were formulated by the first author. Conjecture 1. If n >>-2k, n =/ = 4, then sr(Pn, k) = n for k large enough. Conjecture 2. There is a function f : N---> N such that if n >~ f ( k ), then sr(Pn, k) = n.