3
$\begingroup$

A graph property is hereditary if it is closed under taking induced subgraphs (equivalently, if it is closed under removing vertices). A graph property is monotone if it is closed under taking subgraphs. (Note that "monotone" is sometimes used in different ways from what I've just written.) Thus, every monotone property is hereditary (but not conversely). Every monotone property can be characterized by a set of forbidden subgraphs, and every hereditary property can be characterized by a set of forbidden induced subgraphs. (In each case, the set of forbidden graphs may be infinite.)

Given a (monotone or hereditary) property $\mathcal{P}$, it's easy to define a set $\mathcal{F}$ of forbidden subgraphs (or forbidden induced subgraphs): if $\mathcal{U}$ is the set of all finite unlabeled graphs, set $\mathcal{F} = \mathcal{U} \setminus \mathcal{P}$. However, this is not very useful. Many hereditary properties can be characterized by simpler set of forbidden subgraphs: for example, perfect graphs are exactly the graphs with no induced $C_{2k+1}$ or $\overline{C_{2k+1}}$ for any $k \geq 2$.

However, I'm having a harder time coming up with examples of monotone properties that have "non-trivial" characterizations in terms of forbidden subgraphs. Of course, for any graph $H$, the class of $H$-free graphs is trivially characterized by taking $\mathcal{F} = \{H\}$. The only other example that comes to mind is bipartite graphs, which are characterized by forbidding odd cycles.

What other examples are there?

Improve this question
$\endgroup$
1
  • $\begingroup$ linegraphs is a nice example. $\endgroup$
    – Brendan McKay
    May 22, 2014 at 15:31

3 Answers 3

Reset to default
3
$\begingroup$

Kuratowski's theorem gives such a characterization of planarity.

Also, Google says there are analogues of this theorem for other surfaces. This should give a rather wide class of examples.

EDIT: I just noticed there is a nice list of properties characterized by forbidden subgraphs on Wikipedia.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That's true, a list of forbidden minors does give a compact representation of a class of forbidden subgraphs. $\endgroup$
    – Andrew Uzzell
    May 22, 2014 at 13:29
  • 1
    $\begingroup$ In the case of graphs on surfaces we get a finite list of graphs so that a graph which is cannot be embedded must contain a subdivision of a graph from the list. $\endgroup$
    – Gil Kalai
    May 23, 2014 at 8:07
1
$\begingroup$

Several of these are listed at https://en.wikipedia.org/wiki/Forbidden_graph_characterization

See in particular the ones there labeled either "subgraph" or "homeomorphic subgraph" (the latter meaning that the forbidden subgraphs themselves are subdivisions of the graphs listed).

Improve this answer
$\endgroup$
0
$\begingroup$

There are some results about $P_n$-free graphs. For example;

A graph $G$ is $P_4$-free if and only if each connected induced subgraph of $G$ contains a dominating induced $C_4$ or a dominating vertex.

Also, $P_6$-free graphs are studied.

In spectral graph theory, forbidden induced subgraphs plays an important rules for graph characterizations. One of very interesting paper in this direction is:

"The graphs with all but two eigenvalues equal to $\pm 1$".

I hope it was helpful.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.