A variant of the classical Ramsey problem
The following quantity is estimated. Let \(f(n,p,q)\) be the minimum number of colors needed to color all edges of \(K_n\) such that every \(K_p\) gets at least \(q\) colors. A general upper bound is given using the Lovász local lemma. If \(q={p\choose 2}-p+3\) then \(f(n,p,q)\) is linear while \(f(n,p,q-1)\) is sublinear. If \(q={p\choose 2}-\lfloor{p\over 2}\rfloor+2\) then \(f(n,p,q)=\Omega(n^2)\) while \(f(n,p,q-1)=O(n^{2-{4\over p}})\) but is \(\Omega(n^{{4\over 3}})\) for \(p\geq 7\). \(f(n,p,p)=\Omega(n^{{1\over{p-2}}})\). Also, \({5\over 6}(n-1)\leq f(n,4,5)\) and \(f(n,9,34)={n\choose 2}-o(n^2)\).
- A generalized Ramsey problem
- On edge colorings with at least \(q\) colors in every subset of \(p\) vertices
- On generalized Ramsey theory: The bipartite case
- A new bound for the Brown-Erdős-Sós problem
- Progress on local properties problems of difference sets
- Polychromatic colorings of 1-regular and 2-regular subgraphs of complete graphs
- The Schur-Erdős problem for semi-algebraic colorings
- Generalized Ramsey numbers: forbidding paths with few colors
- The sub-exponential transition for the chromatic generalized Ramsey numbers
- An explicit edge-coloring of K_n with six colors on every K₅
- Graphs with 4-rainbow index 3 and \(n-1\)
- A construction for difference sets with local properties
- On colorful edge triples in edge-colored complete graphs
- Coloring triple systems with local conditions
- The Erdős-Gyárfás problem on generalized Ramsey numbers
- When is an Almost MonochromaticK4Guaranteed?
- scientific article; zbMATH DE number 4034738 (Why is no real title available?)
- scientific article; zbMATH DE number 734459 (Why is no real title available?)
- An application of the regularity lemma in generalized Ramsey theory
- A (5,5)-Colouring of Kn with Few Colours
- scientific article; zbMATH DE number 881158 (Why is no real title available?)
- Semi-algebraic colorings of complete graphs
- Color isomorphic even cycles and a related Ramsey problem
- Local properties via color energy graphs and forbidden configurations
- Almost-rainbow edge-colorings of some small subgraphs
- New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
- Rainbow generalizations of Ramsey theory: A survey
- Rainbow subgraphs in edge-colored planar and outerplanar graphs
- Lower bounds on the Erdős–Gyárfás problem via color energy graphs
- The Erdős–Gyárfás function with respect to Gallai‐colorings
- Proper edge colorings of Cartesian products with rainbow C₄-s
- Edge colorings avoiding patterns
- New bounds on the generalized Ramsey number \(f(n, 5, 8)\)
- On locally rainbow colourings
- The Erdős-Gyárfás function \(f(n, 4, 5) = \frac{5}{6} n + o(n)\) -- so Gyárfás was right
- Ramsey theory constructions from hypergraph matchings
- Growth rates of the bipartite Erdős-Gyárfás function
- Proper edge colorings of planar graphs with rainbow \(C_4\)-s
- Small Ramsey numbers for books, wheels, and generalizations
- Generalized Ramsey numbers of cycles, paths, and hypergraphs
- A variant of the Erdős-Gyárfás problem for K₈
- Odd-Ramsey numbers of complete bipartite graphs
- Star edge coloring of outerplanar and cubic graphs: bounds and constructions
- A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
- Generalized Ramsey numbers at the linear and quadratic thresholds
- More distinct distances under local conditions
- On generalized Ramsey numbers in the non-integral regime
- The generalized Ramsey number \(f(n,5,8)=\frac{6}{7}n+o(n)\)
- On the quadratic 8-edge case of the Brown-Erdős-Sós problem
- Graph-codes: questions, results and methods
- On the ( k + 2, k)-problem of Brown, Erdős, and Sós for k = 5,6,7
- Distinct distances in planar point sets with forbidden 4-point patterns
- Edge-colorings avoiding rainbow and monochromatic subgraphs
This page was built for publication: A variant of the classical Ramsey problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1280270)
