Induced Subgraphs and Hereditary Graph Classes

Let $H$ and $G$ be finite simple graphs (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets). An induced embedding of $H$ in $G$ is an injection $\phi :V(H)\to V(G)$ such that, for all distinct $x,y\in V(H)$,

$xy\in E(H)⟺\phi (x)\phi (y)\in E(G)\mathrm{.}$

Thus $\phi$ preserves both adjacency and nonadjacency (Injection, surjection, bijection). Its image $G[\phi (V(H))]$ is an induced copy of $H$ in $G$: the restricted map is an isomorphism from $H$ onto that induced subgraph (Subgraphs, induced subgraphs and spanning subgraphs, Graph isomorphisms, automorphisms and graph complements).

We say that $H$ is an induced subgraph of $G$ up to isomorphism when such an embedding exists.

If $\phi :H{\hookrightarrow }_{\mathrm{i}\mathrm{n}\mathrm{d}}G$ and $\psi :G{\hookrightarrow }_{\mathrm{i}\mathrm{n}\mathrm{d}}K$, then $\psi \circ \phi :H{\hookrightarrow }_{\mathrm{i}\mathrm{n}\mathrm{d}}K$. Consequently, being an induced subgraph up to isomorphism is transitive.

For finite graphs $H$ and $G$, define the induced-embedding count

${\mathrm{ind}}_H(G):=\mathrm{\mid }\{\phi :V(H)\to V(G):\phi \text{ is an induced embedding}\}\mathrm{\mid }\mathrm{.}$

The set inside the cardinality is a subset of the finite function set $V(G{)}^{V(H)}$, so the displayed natural number is well defined (The set $A^B$ of functions $B\to A$ between finite sets is finite, with $\mid A^B\mid =\mid A{\mid }^{\mid B\mid }$, A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$, The cardinality $\mid A\mid$ of a finite set).

This convention counts labelled embeddings, not vertex subsets. An induced copy with image $W$ contributes one embedding for each isomorphism $H\to G[W]$ (Induced embeddings and induced copies of a graph).

If $H\cong H^{\mathrm{\prime }}$ and $G\cong G^{\mathrm{\prime }}$, then

${\mathrm{ind}}_H(G)={\mathrm{ind}}_{H^{\mathrm{\prime }}}(G^{\mathrm{\prime }})\mathrm{.}$

Moreover,

${\mathrm{ind}}_H(G)={\mathrm{ind}}_{\bar{H}}(\bar{G})\mathrm{.}$

For finite graphs $H$ and $G$, the graph $G$ is $H$-free when $G$ has no induced copy of $H$ (Induced embeddings and induced copies of a graph). Equivalently,

${\mathrm{ind}}_H(G)=0$

(The induced-embedding count ${\mathrm{ind}}_H(G)$).

For a family $\mathcal{F}$ of finite graphs, a finite graph $G$ is $\mathcal{F}$-free when it is $H$-free for every $H\in \mathcal{F}$. Throughout this page, “free” always refers to induced subgraphs. It does not merely prohibit ordinary subgraph copies.

If $G$ is $\mathcal{F}$-free and $J$ is an induced subgraph of $G$, then $J$ is $\mathcal{F}$-free.

A class $\mathcal{C}$ of finite simple graphs is a hereditary graph class when:

1. it is closed under isomorphism; and
2. whenever $G\in \mathcal{C}$ and $H$ has an induced embedding into $G$, one has $H\in \mathcal{C}$.

The second clause is closure under taking induced subgraphs (Induced embeddings and induced copies of a graph). Isomorphism closure makes membership depend only on graph structure, not on the chosen vertex labels (Graph isomorphisms, automorphisms and graph complements).

For every family $\mathcal{F}$ of finite graphs, the class of all $\mathcal{F}$-free finite graphs is hereditary.

Let $\mathcal{C}$ be a hereditary class. A finite graph $H$ is a minimal forbidden induced subgraph for $\mathcal{C}$ when

$H\mathrm{\notin }\mathcal{C},$

but every proper induced subgraph $H[W]$ with $W⊊V(H)$ belongs to $\mathcal{C}$ (Subgraphs, induced subgraphs and spanning subgraphs).

The minimal forbidden basis $\mathcal{B}(\mathcal{C})$ is the class of all such graphs, understood up to isomorphism. More generally, a family $\mathcal{F}$ is a forbidden induced-subgraph basis for $\mathcal{C}$ when $G\in \mathcal{C}$ exactly when $G$ is $\mathcal{F}$-free ($H$-free and $\mathcal{F}$-free graphs under the induced-subgraph convention). Minimality here concerns proper induced subgraphs, not ordinary subgraphs (Induced embeddings and induced copies of a graph, Hereditary graph classes).

For every hereditary graph class $\mathcal{C}$ and every finite graph $G$,

$G\in \mathcal{C}⟺G\text{ is }\mathcal{B}(\mathcal{C})\text{-free}\mathrm{.}$

If $\mathcal{F}$ is any forbidden induced-subgraph basis for $\mathcal{C}$, then for every $H\in \mathcal{B}(\mathcal{C})$, the family $\mathcal{F}$ contains a graph isomorphic to $H$. Consequently, $\mathcal{B}(\mathcal{C})$ is, up to isomorphism, the unique inclusion-minimal forbidden basis for $\mathcal{C}$.

Every nonempty hereditary class of finite graphs contains the null graph $K_0$.

For a graph class $\mathcal{C}$, its complement class is

$\bar{\mathcal{C}}:=\{G:\bar{G}\in \mathcal{C}\}\mathrm{.}$

It consists exactly of those graphs whose complements belong to $\mathcal{C}$. If $\mathcal{C}$ is isomorphism-closed, this is equivalently the isomorphism-closed class of complements of members of $\mathcal{C}$ (Graph isomorphisms, automorphisms and graph complements). The notation does not mean set-theoretic complement inside the class of all graphs.

When $\mathcal{C}$ is isomorphism-closed, so is $\bar{\mathcal{C}}$, because an isomorphism of graphs induces an isomorphism of their complements.

For every finite graph $G$ and every $W\subseteq V(G)$,

$\overline{G[W]}=\bar{G}[W]$

as graphs on vertex set $W$.

If $\mathcal{C}$ is hereditary, then $\bar{\mathcal{C}}$ is hereditary and

$\mathcal{B}(\bar{\mathcal{C}})=\{\bar{H}:H\in \mathcal{B}(\mathcal{C})\}$

up to isomorphism.

For finite graphs $G$ and $H$,

$G\text{ is }H\text{-free}⟺\bar{G}\text{ is }\bar{H}\text{-free}\mathrm{.}$

Let $G$ be a finite simple graph. A set $X\subseteq V(G)$ is a clique when every two distinct vertices of $X$ are adjacent, equivalently when $G[X]$ is complete. It is a stable set, or independent set, when no two distinct vertices of $X$ are adjacent, equivalently when $G[X]$ is edgeless (Subgraphs, induced subgraphs and spanning subgraphs, Empty and complete graphs, complete bipartite graphs, and the convention that $P_n$ and $C_n$ have $n$ vertices).

The clique number and stability number are

$\omega (G):=\max \{\mathrm{\mid }X\mathrm{\mid }:X\text{ is a clique in }G\},\alpha (G):=\max \{\mathrm{\mid }X\mathrm{\mid }:X\text{ is a stable set in }G\}\mathrm{.}$

Both maxima exist because the families are nonempty, containing $\mathrm{\varnothing }$, and lie inside the finite power set of $V(G)$ (The cardinality $\mid A\mid$ of a finite set, $\mid \mathcal{P}(A)\mid =2^{\mid A\mid }$ for finite $A$, A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$, The well-ordering principle). In particular, $\omega (K_0)=\alpha (K_0)=0$.

For every finite graph $G$, a vertex set is a clique in $G$ if and only if it is a stable set in $\bar{G}$. Consequently,

$\omega (\bar{G})=\alpha (G),\alpha (\bar{G})=\omega (G)\mathrm{.}$

A graph $G$ is anticonnected, or co-connected, when its complement $\bar{G}$ is connected (Connected graphs and connected components defined by the existence of vertex paths, Graph isomorphisms, automorphisms and graph complements).

An anticonnected component, or anticomponent, of $G$ is a vertex set $A\subseteq V(G)$ that is the vertex set of a connected component of $\bar{G}$. Equivalently, $G[A]$ is anticonnected and $A$ is inclusion-maximal with that property (Subgraphs, induced subgraphs and spanning subgraphs).

Under the library convention, the null graph is not anticonnected, while a one-vertex graph is anticonnected.

For every graph $G$, its anticomponents are exactly the vertex sets of the connected components of $\bar{G}$. In particular, they partition $V(G)$.

Every finite graph with at least two vertices is connected or anticonnected. Equivalently, if $G$ is disconnected and nontrivial, then $\bar{G}$ is connected.

Let $G$ be a finite simple graph and let $A,B\subseteq V(G)$ be disjoint. An edge between $A$ and $B$ is an edge $ab$ with $a\in A$ and $b\in B$.

The pair $(A,B)$ is:

• complete when every $a\in A$ is adjacent to every $b\in B$;
• anticomplete when no $a\in A$ is adjacent to any $b\in B$;
• pure when it is complete or anticomplete; and
• mixed when it is neither complete nor anticomplete.

Adjacency is the symmetric edge relation of $G$ (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets, Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree). If $A=\mathrm{\varnothing }$ or $B=\mathrm{\varnothing }$, the pair is both complete and anticomplete, hence pure and not mixed.

For disjoint vertex sets $A,B$ in a graph $G$:

1. $(A,B)$ is complete, anticomplete, pure or mixed exactly when $(B,A)$ has the same property;
2. complementation swaps complete pairs with anticomplete pairs; and
3. complementation preserves pure pairs and mixed pairs.

Distinct connected components of a graph are anticomplete to one another. Distinct anticomponents are complete to one another.