Extremal theory and bipartite graph-tree Ramsey numbers

✍ Scribed by P. Erd'́os; R.J. Faudree; C.C. Rousseau; R.H. Schelp

• Publisher: Elsevier Science
• Year: 1988
• Tongue: English
• Weight: 675 KB
• Volume: 72
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(88)90198-7

✦ Synopsis

For a positive integer n and graph E, fs(n) is the least integer m such that any graph of order n and minimal degree m has a copy of B. It will be show that if B is a bipartite graph with parts of order k and 1 (k G I), then there exists a positive constant c, such that for any tree T,, of order II and for any j (0 c j c (k -l)), the Ramsey number

r(T,, Z?) G n + c . (&(n))"'*-'I if A(T,) c (n/(k -j -1)) -(j + 2) . f&).

In particular, this implies r(T,, B) is bounded above by n + o(n) for any tree T, (since fs(n) = o(n) when B is a bipartite graph), and by n + O(1) if the tree T, has no vertex of large degree. For special classes of bipartite graphs, such as even cycles, sharper bounds will be proved along with examples demonstrating their sharpness. Also, applications of this to the determination of Ramsey number for arbitrary graphs and trees will be discussed.