Ramsey goodness of books revisited

For two graphs $G, H$, their Ramsey number $r(G, H)$ is the smallest $N$ such that every graph $\Gamma$ 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(K_p, H) = (p - 1)(n - 1) + 1$, where $K_p$ 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 \geq k \geq 1$, the $k$-book graph $B_{k,n}$ is the graph on $n$ vertices consisting of a copy of $K_k$, 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 $B_{k,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$.