Premium
On induced Ramsey numbers for multiple copies of graphs
Author(s) -
Axenovich Maria,
Gorgol Izolda
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22557
Subject(s) - combinatorics , mathematics , ramsey's theorem , multipartite , discrete mathematics , cograph , vertex (graph theory) , indifference graph , ramsey theory , pathwidth , 1 planar graph , graph , chordal graph , line graph , physics , quantum mechanics , quantum entanglement , quantum
We say that a graph F strongly arrows a pair of graphs ( G , H ) and write F → ind ( G , H ) if any coloring 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 min { | V ( F ) | : F → ind ( G , H ) } . We consider the connection between the induced Ramsey number for a pair of two connected graphs IR ( G , H ) and the induced Ramsey number for multiple copies of these graphs IR ( s G , t H ) , where x G denotes the pairwise vertex‐disjoint union of x copies of G . It is easy to see that if F → ind ( G , H ) , then ( s + t − 1 ) F → ind ( s G , t H ) . This implies that IR ( s G , t H ) ≤ ( s + t − 1 ) IR ( G , H ) .For several specific graphs, such as a path on three vertices vs a complete multipartite graph, a matching vs a complete graph, or a matching vs another matching, it is known that the above inequality is tight. On the other hand, the inequality is also strict for some graphs. However, even in the simplest case when H is an edge and t = 2 , it is not known for what G and for what s the above inequality is tight. We show that it is tight if G is connected and s is at least as large as the order of G . In addition, we make further progress in determining induced Ramsey numbers for multiple copies of graphs, such as paths and triangles.