Existence of the base graph A

PDF p. 3: Section 3, paragraph beginning First

Let $H_1,H_2$ be non-isomorphic finite connected simple graphs, each with an edge, ordered so that $\beta (H_1)\ge \beta (H_2)$ and, when equality holds, $\mathrm{\mid }{H}_1\mathrm{\mid }\ge \mathrm{\mid }{H}_2\mathrm{\mid }$. Let $I$ be an independent set of $H_2$ such that $F=H_2-I$ satisfies $\beta (F)<\beta (H_2)$, and let $k\ge 1$ be an integer. Then there is a graph $A\in \mathrm{Forb}(H_1)\cap {\mathcal{R}}_{\mathrm{i}\mathrm{n}\mathrm{d}}^k(F)$.

Here $H_2-I$ is the induced graph on the vertices outside $I$, and independent means that no edge has both endpoints in $I$. A block is a maximal 2-connected subgraph or a bridge with its endpoints; a 2-connected graph has at least three vertices, is connected, and remains connected after deletion of any one vertex. A bridge is an edge whose deletion increases the number of connected components. For a graph with an edge, $\beta$ is the largest block order; for an edgeless nonempty graph it is $1$. Graph order is the number of vertices, and $\mathrm{\parallel }B\mathrm{\parallel }$ denotes the number of edges of $B$.

The class $\mathrm{Forb}(H_1)$ consists of nonempty finite simple graphs containing no induced copy of $H_1$. The class ${\mathcal{R}}_{\mathrm{i}\mathrm{n}\mathrm{d}}^k(F)$ consists of such graphs in which every assignment of $k$ available colours to the vertices has a monochromatic induced copy of $F$. An induced copy preserves both adjacency and nonadjacency.

If $F$ is edgeless, one may take $A$ edgeless on $k(\mathrm{\mid }F\mathrm{\mid }-1)+1$ vertices. Otherwise, choose a block $B$ of $H_1$ of order $\beta (H_1)$ and take any graph $A=G(F,\mathrm{\parallel }B\mathrm{\parallel }+2,k)$ supplied by Construction 1. This construction places copies of $F$ on the hyperedges of a suitable finite uniform hypergraph of the specified girth and chromatic property; its choices are as in Construction 1: graph G(H,q,k).