# Upper bound on r(tree, complete multi-partite)

Home

Search

Subjects

About Erdös

About This Site

Search

Subjects

- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)

About Erdös

About This Site

For two graphs \( G\) and \( H\), let \( r(G,H)\) denote the smallest integer \( m\) satisfying the property that if the edges of the complete graph \( K_m\) are colored in red and blue, then there is either a subgraph isomorphic to \( G\) with all red edges or a subgraph isomorphic to \( H\) with all blue edges. The classical Ramsey numbers are those for the complete graphs and are denoted by \( r(s,t)= r(K_s, K_t)\).

Chvátal [1] proved that

\(\displaystyle r(T,K_m) = (m-1)(n-1)+1 \)

for any tree on \( n\) vertices. This result was generalized to graphs with small chromatic number. For a graph \( G\) with chromatic number \( \chi(G)\),
it was shown [3] that
\(\displaystyle r(T, G) = (\chi(G)-1)(n-1)+1\)

for any tree \( T\) on \( n\) vertices, provided \( n\) is sufficiently large.

** Conjecture** [2]

If \(m_1 \leq \ldots \leq m_k\), then
\[ r(T,K_{m_1,\ldots,m_k}) \leq (\chi(G) -1) (r(T,K_{m_1,m_2})-1)+ m_1 \]
where \(T\) is any tree on \(n\) vertices, and \(n\) is large enough.