Name
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 Erdős-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(st2) 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,Pt)=O(stlogt), which differs only by a logarithmic factor from the conjecture. This substantially improves the previous bounds for most values of s and t. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.endm.2007.07.008 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Constrained Ramsey number,monochromatic,rainbow,median order | Edge coloring,Discrete mathematics,Complete graph,Combinatorics,Vertex (geometry),Ramsey's theorem,Isomorphism,Logarithm,Rainbow,Conjecture,Mathematics | Journal |
Volume | ISSN | Citations |
29 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 7 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Po-Shen Loh | 1 | 133 | 18.68 |
| Benny Sudakov | 2 | 1391 | 159.71 |