On generalized Ramsey numbers for trees (Q1062076): Difference between revisions

Let G be a finite graph and k a natural number. We define r(G,k) to be the smallest natural number r so that, if the edges of \(K_ r\) (the complete graph on r vertices) are colored with k colors, then there is always a monochromatic copy of G (i.e. a subgraph of \(K_ r\) isomorphic to G with all of its edges colored the same color). Given natural numbers n, \(k\geq 2\), we define r(\({\mathcal T}_ n,k)\) to be the smallest natural number r so that, if the edges of \(K_ r\) are colored with k colors, there exists a monochromatic, connected subgraph with more than n vertices. One easily sees that \(r(G,k)\geq r({\mathcal T}_ n,k)\) for any connected graph G with more than n vertices. This inequality is particularly relevant if G is a tree. This paper is devoted to computing both lower and upper bounds for r(\({\mathcal T}_ n,k)\) and exact values for some infinite sets of pairs (n,k). The proofs involve constructions using Latin squares and resolvable block designs.