I'm new to graph theory and got confused with the following two notions
- Forbidden subgraphs: Given a graph, it's a set of subgraphs that don't contain graphs isomorphic to particular graph
- H-free graphs: graphs not containing any induced subgraph isomorphic to a given graph H
It seems that they are meaning a set of graphs that don't contain specific graph…
Am I understanding correctly..?
Best Answer
We call a family $\mathcal{G}$ of graphs $H$-free if no $G \in \mathcal{G}$ contains $H$ as an induced subgraph.
We call $H$ the forbidden subgraph for the family $\mathcal{G}$ and we sometimes say that $\mathcal{G}$ is defined in terms of forbidden induced subgraphs or in terms of the forbidden induced subgraph $H$.
This can be generalized to a set $\mathcal{H}$ of graphs. We define a family of graphs that does not contain any graph $H \in \mathcal{H}$ as an induced subgraph.
For example a family of graphs could be $(C_5, P_5)$-free that is the family of graphs that does neither contain $C_5$ nor $P_5$ as an induced subgraph.
Edit: In response to Misha's comment. The notion of $H$-freeness is actually not restricted to forbidding an induced subgraph. In general we speak of Forbidden Graph Characterization which summarizes different notions for defining a family of graphs in terms of forbidden graph structures, including forbidden induced subgraphs, forbidden subgraphs (not necessarily induced), graph minors, ... Note that we need to be precise. If we define $H$-freeness, we need to state exactly what we mean, e.g. by providing a definition I have stated above if we mean forbidden induced subgraphs.