Induced Ramsey number for a star versus a fixed graph

Maria Axenovich¹ ; Izolda Gorgol²

¹Department of Mathematics, Karlsruhe Institute of Technology
²Lublin University of Technology

The electronic journal of combinatorics, Tome 28 (2021) no. 1

Résumé

We write $F{\buildrel {\text{ind}} \over \longrightarrow}(H,G)$ for graphs $F, G,$ and $H$, if for any coloring of the edges of $F$ in red and blue, there is either a red induced copy of $H$ or a blue induced copy of $G$. For graphs $G$ and $H$, let $\mathrm{IR}(H,G)$ be the smallest number of vertices in a graph $F$ such that $F{\buildrel {\text{ind}} \over \longrightarrow}(H,G)$. In this note we consider the case when $G$ is a star on $n$ edges, for large $n$ and $H$ is a fixed graph. We prove that $$ (\chi(H)-1) n \leq \mathrm{IR}(H, K_{1,n}) \leq (\chi(H)-1)^2n + \epsilon n,$$ for any $\epsilon>0$, sufficiently large $n$, and $\chi(H)$ denoting the chromatic number of $H$. The lower bound is asymptotically tight for any fixed bipartite $H$. The upper bound is attained up to a constant factor, for example when $H$ is a clique.

Détail

DOI : 10.37236/9358

Classification : 05C55, 05D10
Mots-clés : chromatic number, induced Ramsey number