Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-11T17:52:25.427Z Has data issue: false hasContentIssue false
  • English
  • Français

A (5,5)-Colouring of Kn with Few Colours

Part of: Extremal combinatorics Graph theory

Published online by Cambridge University Press:  09 May 2018

ALEX CAMERON  and
EMILY HEATH
ALEX CAMERON
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, IL 60607, USA (e-mail: acamer4@uic.edu)
EMILY HEATH
Affiliation:
Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA (e-mail: eheath3@illinois.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

For fixed integers p and q, let f(n,p,q) denote the minimum number of colours needed to colour all of the edges of the complete graph Kn such that no clique of p vertices spans fewer than q distinct colours. Any edge-colouring with this property is known as a (p,q)-colouring. We construct an explicit (5,5)-colouring that shows that f(n,5,5) ≤ n1/3 + o(1) as n → ∞. This improves upon the best known probabilistic upper bound of O(n1/2) given by Erdős and Gyárfás, and comes close to matching the best known lower bound Ω(n1/3).

MSC classification

Primary: 05C55: Generalized Ramsey theory
Secondary: 05C35: Extremal problems 05C25: Graphs and abstract algebra (groups, rings, fields, etc.) 05D10: Ramsey theory
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 6 , November 2018 , pp. 892 - 912
Copyright
Copyright © Cambridge University Press 2018 

References

[1] Axenovich, M. (2000) A generalized Ramsey problem. Discrete Math. 222 247–249.Google Scholar
[2] Babai, L. and Frankl, P. (1992) Linear Algebra Methods in Combinatorics: With Applications to Geometry and Computer Science, Department of Computer Science, University of Chicago.Google Scholar
[3] Conlon, D., Fox, J., Lee, C. and Sudakov, B. (2015) The Erdős–Gyárfás problem on generalized Ramsey numbers. Proc. London Math. Soc. 110 1–18.Google Scholar
[4] Eichhorn, D. and Mubayi, D. (2000) Edge-coloring cliques with many colors on subcliques. Combinatorica 20 441–444.Google Scholar
[5] Erdős, P. (1975) Problems and results on finite and infinite graphs. In Recent Advances in Graph Theory (Proc. Second Czechoslovak Sympos., Prague, 1974), pp. 183–192.Google Scholar
[6] Erdős, P. (1981) Solved and unsolved problems in combinatorics and combinatorial number theory. Europ. J. Combin. 2 1–11.Google Scholar
[7] Erdős, P. and Gyárfás, A. (1997) A variant of the classical Ramsey problem. Combinatorica 17 459–467.Google Scholar
[8] Krop, E. and Krop, I. (2013) Almost-rainbow edge-colorings of some small subgraphs. Discussiones Mathematicae Graph Theory 33 771–784.Google Scholar
[9] Mubayi, D. (1998) Edge-coloring cliques with three colors on all 4-cliques. Combinatorica 18 293–296.Google Scholar
[10] Mubayi, D. (2004) An explicit construction for a Ramsey problem. Combinatorica 24 313–324.Google Scholar
[11] Mubayi, D. (2016) Coloring triple systems with local conditions. J. Graph Theory 81 307–311.Google Scholar
[12] Perelli, A., Pintz, J. and Salerno, S. (1984) Bombieri's theorem in short intervals. Annali della Scuola Normale Superiore di Pisa–Classe di Scienze 11 529–539.Google Scholar