A generalized Ramsey problem
type: Item
instance of: scholarly article
title: A generalized Ramsey problem
zbMATH Open document ID: 0969.05042
DOI: 10.1016/S0012-365X(00)00052-2
published in: Discrete Mathematics
publication date: 2000-09-14T00:00:00Z
review text: Let \(f(n)\) be the minimum number such that there is a proper edge-coloring of \(K_n\), the complete graph on \(n\) vertices using \(f(n)\) colors with no path or cycle of 4 edges using one or two colors. Let \(f(n,p,q)\) denote the minimal number of colors needed to color the edges of \(K_n\) such that \(p\)-clique uses at least \(q\) colors on its edges. The author develops the relationship between \(f(n)\) and \(f(n,5,9)\) and exploits that relationship to prove: \hskip 10mm Theorem 1. \hskip 10mm (i) \({1+ \sqrt 5\over 2} n-3\leq f(n)\leq 2n^{1+ c/\sqrt{\log n}}\), \hskip 10mm (ii) \({1+\sqrt 5\over 2} n-3\leq f(n,5,9)\leq 2n^{1+ c/\sqrt{\log n}}\), where \(c\) is a positive constant.
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 1506832
zbMATH Keywords: generalized Ramsey problem
zbMATH Keywords: edge-coloring
author: Maria Axenovich
reviewed by: Jack E. Graver
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00052-2
OpenAlex ID: W2044397349
description: scientific article; zbMATH DE number 1506832