2017/10/26 by Gorgol, Izolda
#05C55 #05D10 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1710.09850
We say that a graph F strongly arrows a pair of graphs (G,H) if any 2-colouring of its edges with red and blue leads to either a red G or a blue H appearing as induced subgraphs of F. The induced Ramsey number, IR(G,H) is defined as the minimum number of vertices of a graph F which strongly arrows a pair (G,H). We will consider two aspects of induced Ramsey numbers. Firstly there will be shown that the lower bound of the induced Ramsey number for a connected graph G with independence number α and a graph H with clique number ω roughly (ω2α)/(2). This bounds is sharp. Moreover we discuss also the case when G is not connected providing also a sharp lower bound which is linear in both parameters