1
$\begingroup$

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..?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ I would add that sometimes, as in the statement of the Erdős–Stone theorem for instance, $H$-free does not mean "induced subgraph" but any kind of subgraph. In general, when $H$ is not a clique, the forbidden subgraph problem would not make sense if we're limiting ourselves to induced subgraphs. $\endgroup$ Feb 13, 2022 at 17:12
  • 1
    $\begingroup$ @MishaLavrov you are exactly right! I have added it to my answer. $\endgroup$ Feb 13, 2022 at 21:01
  • $\begingroup$ Hi David!! Thank you for your answer again!! sorry, I have one deadline next Monday,,, But I need to understand this so let me get back here after the deadline!! $\endgroup$
    – Rowing0914
    Feb 15, 2022 at 23:11
  • $\begingroup$ @MishaLavrov, That makes sense!! Sorry for late reply but thank you for clarification! $\endgroup$
    – Rowing0914
    Feb 22, 2022 at 23:35
  • $\begingroup$ @DavidScholz, Thank you for editing my question and for the detailed answer!! I feel more comfortable in these notions now! $\endgroup$
    – Rowing0914
    Feb 22, 2022 at 23:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .