# Natural graph class with five excluded subgraphs?

I'm interested in hereditary graph classes characterized by a small number of excluded subgraphs. There are some well-known graph classes that are characterized by three or four obstructions -- examples are threshold graphs, chain grapns and trivially perfect graphs. My question is: are there natural graph classes characterized by five obstructions? (No relation to the eponymous movie). It may be possible to obtain some by considering the P4-structure of the graph.

• I'm starting to wonder how many of the "super\d" accounts belong to the same person :P.
– R B
Mar 8, 2014 at 9:56
• Does it have to be exactly five or just more than four? If the latter, then the class of line graphs is an answer: en.m.wikipedia.org/wiki/Line_graph Mar 8, 2014 at 10:41
• Just have a look here; you can then decide for yourself what exactly you consider natural out of them, if any :-)
– Juho
Mar 8, 2014 at 13:01
• @Super3 it is easier to participate on the site if you register an account. We can then merge your 4 other accounts with it. Mar 8, 2014 at 15:49
• Is there a motivation for exactly 5 forbidden subgraphs? Mar 9, 2014 at 4:08

The "split-substitute" graphs are the graphs starting with a split graph and substituting any split graph into any node. The forbidden induced subgraphs can be obtains from the forbidden induced subgraphs of split graphs (c4, C5, co-C4), but replacing the non-prime ones (c4 and co-c4) with their minimal prime extensions... (here primality is with respect with modular decomposition.)

So the 5 forbidden induced subgraphs are the C5, P5, co-P5, H6 and co-H6. This forms a self-complementary class which strictly contains the class of cographs.

The maxibrittle graphs are the perfectly orderable graphs for which a vertex sequence defined only by the degrees will produce a perfect order (more specifically, the degree sequence defines a brittle ordering). These graphs have exactly 5 minimal forbidden induced subgraphs.

Graphs where every connected component is a split graph are (C4, C5, P5, necktie, bowtie)-free (see A graph modification approach for finding core–periphery structures in protein interaction networks).

After browsing the ISGCI site I came across the following class: opposition graphs. They seem a possible candidate for your question, but is their obstruction set known?

• I don't see how they can be a candidate... a complete minimal forbidden induced subgraph characterization for them is currently unknown but I'm pretty sure it is known to be infinite.
– JimN
Mar 10, 2014 at 16:50
• Indeed, V B L has given a list of an infinite family of co-bipartite graphs which are minimal non-opposition, as well as an infinite family of trees which are minimal non-opposition graphs in this paper: informatik.uni-rostock.de/~le/Research/coop.pdf
– JimN
Mar 10, 2014 at 16:58
• By the way, do you know a self-contained proof that opposition graphs are perfect? I.e. one that doesn't use Chudnovsky et al. proof of the 'KGT' or the Olariu proof from refs '19-04' in the paper. Apr 9, 2014 at 20:58