Induced forbidden-subgraph class

PDF p. 1: Section 2, first paragraph

Let $H$ be a graph under the conventions of this treatment: a finite simple graph with at least one vertex. The induced forbidden-subgraph class $\mathrm{Forb}(H)$ consists of all such graphs $G$ for which there is no induced copy of $H$ in $G$. Equivalently, there is no injection $\phi :V(H)\to V(G)$ such that, for every pair of distinct vertices $x,y$ of $H$, $xy\in E(H)$ if and only if $\phi (x)\phi (y)\in E(G)$.

Graph and colouring conventions

Induced embeddings and induced copies of a graph

The graph conventions specify the admissible graphs, while the induced-copy definition makes the stated injection condition equivalent to the existence of an induced copy. Negating that condition therefore determines membership for each admissible $G$. The word class permits arbitrary vertex labels and does not require the collection of all such graphs to be a set.