Induced vertex-Ramsey class

PDF p. 1: Abstract; Introduction, first paragraph

Let $H$ be a finite simple graph with at least one vertex, and let $k$ be a positive integer. The induced $k$-colour vertex-Ramsey class of $H$, denoted ${\mathcal{R}}_{\mathrm{i}\mathrm{n}\mathrm{d}}^k(H)$, consists of those finite simple graphs $G$ with at least one vertex for which the following holds: for every function $c:V(G)\to \{1,\dots ,k\}$, there is an injection $\phi :V(H)\to V(G)$ such that $c$ is constant on $\phi (V(H))$ and, for all distinct $x,y\in V(H)$, $\{x,y\}\in E(H)$ if and only if $\{\phi (x),\phi (y)\}\in E(G)$.

Thus the image vertices induce a copy of $H$ and all have the same colour. A colouring need not use every colour, and adjacent vertices may receive the same colour. Membership is understood as a predicate on graphs; no set of all graphs with arbitrary vertex labels is assumed.

The graph conventions specify the finite simple graphs and their vertex and edge sets. The colouring definition supplies the functions and the meaning of constant colour on the image. The induced-embedding definition identifies the displayed adjacency and nonadjacency condition with an induced copy isomorphic to $H$. Consequently the displayed condition determines membership for each graph $G$ without choosing a representative or assuming a universal set of graphs.

Graph and colouring conventions

Unrestricted finite colourings and used palettes

Induced embeddings and induced copies of a graph