Constrained Ramsey Numbers
From MaRDI portal
Abstract: For two graphs S and T, the constrained Ramsey number f(S, T) is the minimum n such that every edge coloring of the complete graph on n vertices, with any number of colors, has a monochromatic subgraph isomorphic to S or a rainbow (all edges differently colored) subgraph isomorphic to T. The Erdos-Rado Canonical Ramsey Theorem implies that f(S, T) exists if and only if S is a star or T is acyclic, and much work has been done to determine the rate of growth of f(S, T) for various types of parameters. When S and T are both trees having s and t edges respectively, Jamison, Jiang, and Ling showed that f(S, T) <= O(st^2) and conjectured that it is always at most O(st). They also mentioned that one of the most interesting open special cases is when T is a path. In this work, we study this case and show that f(S, P_t) = O(st log t), which differs only by a logarithmic factor from the conjecture. This substantially improves the previous bounds for most values of s and t.
Recommendations
Cites work
- A Combinatorial Theorem
- An Upper Bound for Constrained Ramsey Numbers
- Constrained Ramsey numbers of graphs
- Finding a monochromatic subgraph or a rainbow path
- scientific article; zbMATH DE number 2059948 (Why is no real title available?)
- scientific article; zbMATH DE number 2148774 (Why is no real title available?)
- scientific article; zbMATH DE number 2197938 (Why is no real title available?)
- Mono-multi bipartite Ramsey numbers, designs, and matrices
- On pattern Ramsey numbers of graphs
- Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
Cited in
(6)
This page was built for publication: Constrained Ramsey Numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5900067)
