Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-14T05:19:13.605Z 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: [email protected])
EMILY HEATH
Affiliation:
Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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