Hell, Pavol; Montellano-Ballesteros, Juan José Polychromatic cliques. (English) Zbl 1044.05051 Discrete Math. 285, No. 1-3, 319-322 (2004). Summary: The sub-Ramsey number sr(\(K_n,k\)) is the smallest integer \(m\) such that in any edge-colouring of \(K_m\) which uses every colour at most \(k\) times some subgraph \(K_n\) has all edges of different colours. It was known that, for a fixed \(k\), the function sr(\(K_n,k\)) is O(\(n^3\)) and \(\Omega(n)\). We improve these bounds to O(\(n^2\)) and \(\Omega(n^{3/2})\) (slightly less for small values of \(k\)). Cited in 7 Documents MSC: 05C55 Generalized Ramsey theory 05C15 Coloring of graphs and hypergraphs Keywords:Polychromatic; Sub-Ramsey number; Anti-Ramsey; Clique PDFBibTeX XMLCite \textit{P. Hell} and \textit{J. J. Montellano-Ballesteros}, Discrete Math. 285, No. 1--3, 319--322 (2004; Zbl 1044.05051) Full Text: DOI References: [1] Albert, M.; Frieze, A. M.; Reed, B., Multicoloured Hamilton cycles, Electron. J. Combin., 2, R10 (1995) · Zbl 0817.05028 [2] Alspach, B.; Gerson, M.; Hahn, G.; Hell, P., On sub-Ramsey numbers, Ars Combin., 22, 199-206 (1986) · Zbl 0603.05031 [3] Dirac, P., Extension of Turan’s Theorem on Graphs, Acta Math. Sci. Hungar., 14, 417-422 (1963) · Zbl 0113.24703 [4] Erdős, P.; Nešetřil, J.; Rödl, V., On some problems related to partitions of edges of a graph, (Fiedler, M., Graphs and Other Combinatorial Topics (1983), Teubner: Teubner Leipzig), 54-63 [5] Fraisse, P.; Hahn, G.; Sotteau, D., Star sub-Ramsey numbers, Ann. Discrete Math., 34, 153-163 (1987) · Zbl 0629.05047 [6] Frankl, P.; Füredi, Z., A new extremal property of Steiner triple-systems, Discrete Math., 48, 205-212 (1984) · Zbl 0553.05019 [7] Frankl, P.; Füredi, Z., Union-free families of sets and equations over fields, J. Number Theory, 23, 210-218 (1986) · Zbl 0589.05013 [8] Frieze, A.; Reed, B., Polychromatic Hamilton cycles, Discrete Math., 118, 69-74 (1993) · Zbl 0803.05036 [9] Galvin, F., Advanced Problem number 6034, Amer. Math. Monthly, 82, 529 (1975) [10] Hahn, G., Some star anti-Ramsey numbers, Congr. Numer., 19, 303-310 (1977) [11] Hahn, G., More star sub-Ramsey numbers, Discrete Math., 43, 131-139 (1981) · Zbl 0456.05045 [12] Hahn, G.; Thomassen, C., Path and cycle sub-Ramsey numbers and an edge-colouring conjecture, Discrete Math., 62, 29-33 (1986) · Zbl 0613.05044 [13] Lefmann, H.; Rödl, V.; Wysocka, B., Multicolored subsets in colored hypergraphs, J. Combin. Theory Ser. A, 74, 209-248 (1996) · Zbl 0853.05058 [14] Maamoun, M.; Meyniel, H., On a problem of G. Hahn about coloured Hamilton paths in \(K_2n\), Discrete Math., 51, 213-214 (1984) · Zbl 0549.05044 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.