A \((5,5)\)-colouring of \(K_n\) with few colours. (English) Zbl 1402.05145
Summary: 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 \(K_n\) 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)\leq n^{1/3+o(1)}\) as \(n\to\infty\). This improves upon the best known probabilistic upper bound of \(O(n^{1/2})\) given by P. Erdős and A. Gyárfás [Combinatorica 17, No. 4, 459–467 (1997; Zbl 0910.05034)], and comes close to matching the best known lower bound \(\Omega(n^{1/3})\).
MSC:
| 05C55 | Generalized Ramsey theory |
| 05C35 | Extremal problems in graph theory |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C15 | Coloring of graphs and hypergraphs |
| 05D10 | Ramsey theory |
Citations:
Zbl 0910.05034References:
| [1] | Axenovich, M., A generalized Ramsey problem, Discrete Math., 222, 247-249, (2000) · Zbl 0969.05042 · doi:10.1016/S0012-365X(00)00052-2 |
| [2] | Babai, L.; Frankl, P., Linear Algebra Methods in Combinatorics: With Applications to Geometry and Computer Science, (1992), University of Chicago |
| [3] | Conlon, D.; Fox, J.; Lee, C.; Sudakov, B., The Erdős-Gyárfás problem on generalized Ramsey numbers, Proc. London Math. Soc., 110, 1-18, (2015) · Zbl 1306.05148 · doi:10.1112/plms/pdu049 |
| [4] | Eichhorn, D.; Mubayi, D., Edge-coloring cliques with many colors on subcliques, Combinatorica, 20, 441-444, (2000) · Zbl 0959.05041 · doi:10.1007/s004930070016 |
| [5] | Erdős, P., Recent Advances in Graph Theory, Problems and results on finite and infinite graphs, 183-192, (1974), Proc. Second Czechoslovak Sympos.: Proc. Second Czechoslovak Sympos., Prague · Zbl 0347.05116 |
| [6] | Erdős, P., Solved and unsolved problems in combinatorics and combinatorial number theory, Europ. J. Combin., 2, 1-11, (1981) · Zbl 0474.10038 · doi:10.1016/S0195-6698(81)80014-5 |
| [7] | Erdős, P.; Gyárfás, A., A variant of the classical Ramsey problem, Combinatorica, 17, 459-467, (1997) · Zbl 0910.05034 · doi:10.1007/BF01195000 |
| [8] | Krop, E.; Krop, I., Almost-rainbow edge-colorings of some small subgraphs, Discussiones Mathematicae Graph Theory, 33, 771-784, (2013) · Zbl 1295.05151 · doi:10.7151/dmgt.1710 |
| [9] | Mubayi, D., Edge-coloring cliques with three colors on all 4-cliques, Combinatorica, 18, 293-296, (1998) · Zbl 0910.05035 · doi:10.1007/PL00009822 |
| [10] | Mubayi, D., An explicit construction for a Ramsey problem, Combinatorica, 24, 313-324, (2004) · Zbl 1058.05025 · doi:10.1007/s00493-004-0019-6 |
| [11] | Mubayi, D., Coloring triple systems with local conditions, J. Graph Theory, 81, 307-311, (2016) · Zbl 1379.05040 · doi:10.1002/jgt.21876 |
| [12] | Perelli, A.; Pintz, J.; Salerno, S., Bombieri’s theorem in short intervals, Annali della Scuola Normale Superiore di Pisa-Classe di Scienze, 11, 529-539, (1984) · Zbl 0579.10019 |
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.
