Locally Ramsey properties of graphs (Q1115882)

A graph G is local relative to a given k-vertex graph \(H_ k\) if any k vertices of G span a graph that contains \(H_ k\). The local Ramsey number \(R=LR(H_ k,m)\) is the least integer R such that any graph G on R vertices either contains a clique on m vertices or is not local relative to \(H_ k\). Thus, clearly \(LR(H_ k',m)\geq LR(H_ k,m)\) if \(H_ k'\) is a subgraph of \(H_ k\). Local Ramsey numbers for special classes of graphs are determined. For example, the following is proved. Theorem: If \(H_ k\) contains a spanning star as a subgraph and the complement of \(H_ k\) does not contain a perfect matching, then \(LR(H_ k,m)=k- cl(H_ k)+\max \{m,cl(H_ k)\}\), where cl represents the clique number of a graph. Other special graphs considered are those obtained from complete graphs by deleting spanning cycles or paths. Other functions related to the local Ramsey number LR are also considered and results for specific families of graphs are obtained.