On generalized Ramsey numbers for trees

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.

Recommendations

Cites work

Cited in

(27)

This page was built for publication: On generalized Ramsey numbers for trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1062076)