文档介绍：Available online at
Discrete Mathematics 285 (2004) 319–322
Note
Polychromatic cliques
Pavol Hella, Juan JosÃe Montellano-Ballesterosb
aSchool of Computing Science, Simon Fraser University, Burnaby, ., Canada V5A 1S6
bInstituto de Matematicas,à UNAM, Ciudad Universitaria, Mexicoà ., 04510, Mexico
Received 8 July2002; received in revised form 14 December 2003; accepted 9 February2004
Abstract
The sub-Ramseynumber sr( Kn;k) is the smallest integer m such that in anyedge-colouring of Km which uses every
colour at most k times some subgraph Kn has all edges of di2erent colours. It was known that, for a ÿxed k, the function
3 2 3=2
sr(Kn;k)isO(n ) and 8(n). We improve these bounds to O(n ) and 8(n ) (slightlyless for small values of k).
c 2004 Elsevier . All rights reserved.
MSC: 05C15; 05C35
Keywords: Polychromatic; Sub-Ramsey number; Anti-Ramsey; Clique
1. Background and notation
An edge-colouring of a graph G (., a mapping of E(G) to a