On the Ramsey number of trees versus graphs with large clique number

✍ Scribed by Ronald J. Gould; Michael S. Jacobson

• Publisher: John Wiley and Sons
• Year: 1983
• Tongue: English
• Weight: 335 KB
• Volume: 7
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190070109

✦ Synopsis

Chvatal established that r(T,, K,,) = (m -1 ) ( n -1 ) + 1, where T, , , is an arbitrary tree of order m and K, is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K, could be replaced by a graph with clique number n and order n + 5 provided n 2 3 and m 2 3.

We further extend these results t o show that K, can be replaced by any graph on n + 2 vertices w i t h clique number n , provided n 2 5 and m 2 4. W e then show that further extensions, in particular t o graphs on n + 3 vertices with clique number n are impossible. We also investigate the ramsey number of trees versus complete graphs minus sets of independent edges. We show that r ( T , , K, -tK2) = (ml ) ( nt -1) + 1 f o r m 2 3, n 2 6, where T, is any tree of order m except the star, and for each t, 0 5 t 5 [ ( n -2)/2].