For two graphs G,H, their Ramsey number r(G,H) is the smallest N such that every graph Γ on N vertices contains G as a subgraph, or its complement contains H as a subgraph. The existence of r(G,H) is guaranteed by Ramsey’s classical theorem, one of the oldest theorems in graph theory. These innocent-looking numbers are notoriously hard to determine; very few exact values are known. However, in certain cases we are able to determine the Ramsey numbers exactly. For example, a connected graph H on n vertices is called p-good if r(Kp,H)=(p−1)(n−1)+1, where Kp is the complete graph on p vertices. Several p-good graph families are known, for example trees, and there is a rich theory of Ramsey goodness.
For integers n≥k≥1, the k-book graphBk,n is the graph on n vertices consisting of a copy of Kk, called the spine, as well as n−k additional vertices each adjacent to every vertex of the spine and non-adjacent to each other. Book graphs arise naturally in the study of Ramsey numbers. Nikiforov and Rousseau proved that if n is sufficiently large in terms of p and k, then Bk,n is also p-good. Their proof uses Szemerédi’s regularity lemma and thus it gives a tower-type bound on n. In this paper the authors give an elegant new proof for this result that avoids using the regularity method and thus they get a much better dependence for n on k and p.