A note on Ramsey numbers involving large books

Meng Liu ; Yusheng Li

The electronic journal of combinatorics, Tome 31 (2024) no. 1

Résumé

For graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the minimum integer $N$ such that any red/blue edge coloring of $K_N$ contains either a red $G$ or a blue $H$. Let $\chi(G)$ be the chromatic number of $G$, and $s(G)$ the minimum size of a color class over all proper vertex colorings of $G$ with $\chi(G)$ colors. A connected graph $H$ is called $G$-{\em good} if $R(G,H)= (\chi(G)-1)(|H|-1)+s(G)$. For graphs $G$ and $H$, it is shown $K_p+nH$ is $(K_2+G)$-{\em good}, where $n$ is double-exponential in terms of $p,|G|,|H|$, and $K_p+nH$ is $C_{2m+1}$-{\em good} for $n\ge (100q)^{8q^3}$, where $q=\max\{m,p,|H|\}$. Both proofs are short that avoids using the regularity method.

Détail

DOI : 10.37236/11579

Classification : 05C55, 05D10
Mots-clés : chromatic number, Ramsey goodness, Nikiforov-Rousseau theorem