Balla, I; Pokrovskiy, A; Sudakov, B; (2018) Ramsey Goodness of Bounded Degree Trees. Combinatorics, Probability and Computing , 27 (3) pp. 289-309. 10.1017/S0963548317000554.

Preview

Text Ramsey (1).pdf - Accepted Version Download (343kB) | Preview

Abstract

Given a pair of graphs G and H, the Ramsey number R(G, H) is the smallest N such that every red-blue coloring of the edges of the complete graph KN contains a red copy of G or a blue copy of H. If a graph G is connected, it is well known and easy to show that R(G, H) ≥ (|G| − 1)(χ(H) − 1) + σ(H), where χ(H) is the chromatic number of H and σ(H) is the size of the smallest color class in a χ(H)-coloring of H. A graph G is called H-good if R(G, H) = (|G| − 1)(χ(H) − 1) + σ(H). The notion of Ramsey goodness was introduced by Burr and Erd˝os in 1983 and has been extensively studied since then. In this paper we show that if n ≥ Ω(|H| log4 |H|) then every n-vertex bounded degree tree T is H-good. The dependency between n and |H| is tight up to log factors. This substantially improves a result of Erd˝os, Faudree, Rousseau, and Schelp from 1985, who proved that n-vertex bounded degree trees are H-good when n ≥ Ω(|H| 4 ). MSC: 05C05, 05C55

Download activity - last month

Export as CSVJSONXML

Download activity - last 12 months

Export as XMLJSONCSV

Downloads by country - last 12 months

Export as CSVJSONXML

Archive Staff Only

View Item