# Induced ramsey number for a star versus a fixed graph

Axenovich, Maria; Gorgol, Izolda

##### Abstract:
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 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 χ(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.

 Zugehörige Institution(en) am KIT Institut für Algebra und Geometrie (IAG) Publikationstyp Zeitschriftenaufsatz Publikationsjahr 2021 Sprache Englisch Identifikator ISSN: 1077-8926, 1097-1440, 2150-959X, 2156-3527 KITopen-ID: 1000131166 Erschienen in Electronic Journal of Combinatorics Verlag Electronic Journal of Combinatorics Band 28 Heft 1 Seiten Art.-Nr.: P1.55 Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page