KIT | KIT-Bibliothek | Impressum | Datenschutz

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.


Verlagsausgabe §
DOI: 10.5445/IR/1000131166
Veröffentlicht am 13.04.2021
Cover der Publikation
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 Web of Science
Scopus
Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page