Ordinary 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 ordinary $k$-colour vertex-Ramsey class of $H$, denoted ${\mathcal{R}}^k(H)$, consists of all 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 a subgraph $J$ of $G$ isomorphic to $H$ such that $c$ is constant on $V(J)$.

A subgraph has a subset of the host's vertices and a subset of its edges; an isomorphism is a bijection of vertex sets preserving and reflecting adjacency. Thus $J$ is an ordinary copy of $H$: edges of $G$ between vertices of $J$ may be absent from $J$. The function $c$ is an unrestricted $k$-colouring: it need not use every colour, and adjacent vertices may receive the same colour. Constant colour on $V(J)$ means that the copy is monochromatic.

The graph conventions specify finite simple graphs, subgraphs and isomorphisms. The colouring definition supplies the stated functions and monochromatic condition, including unused colours. The ordinary embedding definition identifies an isomorphic subgraph with an injective edge-preserving map from $H$ into $G$: its image vertices and image edges form the copy, while extra host edges are allowed. Consequently the displayed membership condition is definite and does not impose inducedness or proper colouring. Here “class” denotes the collection specified by this condition; no universal set of all graphs is assumed.

Graph and colouring conventions

Unrestricted finite colourings and used palettes

Ordinary embeddings as injections preserving edges