<p>The "<strong>split-substitute</strong>" 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.)</p>

<p>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.</p>

<p>See: <a href="http://webdocs.cs.ualberta.ca/~hayward/papers/p4comp.online.pdf" rel="nofollow">http://webdocs.cs.ualberta.ca/~hayward/papers/p4comp.online.pdf</a></p>

<hr>

<p>The <strong>maxibrittle</strong> 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.</p>

CC BY-SA 3.0
2014-03-10T08:10:33.680Z
2014-03-10T08:26:22.983Z
2014-03-10T08:26:22.983Z
JimN
<p>Graphs where every connected component is a split graph are (C4, C5, P5, necktie, bowtie)-free (see <a href="http://dx.doi.org/10.1186%2Fs13015-015-0043-7" rel="nofollow">A graph modification approach for finding core–periphery structures in protein interaction networks</a>).</p>

CC BY-SA 3.0
2016-03-17T10:15:14.000Z
2016-03-17T10:15:14.000Z
Falk Hüffner
<p>After browsing the <a href="http://www.graphclasses.org/" rel="nofollow">ISGCI</a> site I came across the following class: <a href="http://www.graphclasses.org/classes/gc_89.html" rel="nofollow">opposition graphs</a>.
They seem a possible candidate for your question, but is their obstruction set known?</p>

CC BY-SA 3.0
2014-03-10T16:50:26.017Z
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
CC BY-SA 3.0
2014-03-10T16:58:09.900Z
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: http://www.informatik.uni-rostock.de/~le/Research/coop.pdf
JimN
CC BY-SA 3.0
2014-04-09T20:58:11.590Z
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.
Super8
CC BY-SA 3.0
2014-03-10T11:57:56.087Z
2014-04-09T21:51:58.463Z
2014-04-09T21:51:58.463Z
MarchMadness
<p>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.</p>

CC BY-SA 3.0
2014-03-08T09:56:45.380Z
I'm starting to wonder how many of the "super\d" accounts belong to the same person :P.
R B
CC BY-SA 3.0
2014-03-08T10:41:57.873Z
Does it have to be exactly five or just more than four? If the latter, then the class of line graphs is an answer: http://en.m.wikipedia.org/wiki/Line_graph
Tyson Williams
CC BY-SA 3.0
2014-03-08T13:01:09.063Z
Just have a look [here](http://www.graphclasses.org/classes.cgi); you can then decide for yourself what exactly you consider natural out of them, if any :-)
Juho
CC BY-SA 3.0
2014-03-08T13:38:29.367Z
To R B: yes, they belong to the same person, I'm just alternating between "circle-shaped digits" like 0/3/5/9.
Super3
CC BY-SA 3.0
2014-03-08T13:46:50.430Z
To Juho: I think the website contain one interesting such class, but there may exist several other ones "in the limbo".
Super3
CC BY-SA 3.0
2014-03-08T15:49:36.603Z
@Super3 it is easier to participate on the site if you register an account. We can then merge your 4 other accounts with it.
Artem Kaznatcheev
CC BY-SA 3.0
2014-03-09T04:08:06.340Z
Is there a motivation for exactly 5 forbidden subgraphs?
Vinicius dos Santos
<graph-theory><graph-classes>
Natural graph class with five excluded subgraphs?
Super3
# Natural graph class with five excluded subgraphs?

(Asked by: username_0 on 2014-03-08)

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.

**Tags:** graph-theory, graph-classes
> **Comments:**
> **username_1**: I'm starting to wonder how many of the "super\d" accounts belong to the same person :P.  
> **username_2**: Does it have to be exactly five or just more than four? If the latter, then the class of line graphs is an answer: http://en.m.wikipedia.org/wiki/Line_graph  
> **username_3**: Just have a look [here](http://www.graphclasses.org/classes.cgi); you can then decide for yourself what exactly you consider natural out of them, if any :-)  
> **username_0**: To R B: yes, they belong to the same person, I'm just alternating between "circle-shaped digits" like 0/3/5/9.  
> **username_0**: To Juho: I think the website contain one interesting such class, but there may exist several other ones "in the limbo".  
> **username_4**: @Super3 it is easier to participate on the site if you register an account. We can then merge your 4 other accounts with it.  
> **username_5**: Is there a motivation for exactly 5 forbidden subgraphs?  

---

## 3 answers

### Answer by username_6 on 2014-03-10. Score: 3

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.

See: <http://webdocs.cs.ualberta.ca/~hayward/papers/p4comp.online.pdf>

---

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.


---

### Answer by username_7 on 2016-03-17. Score: 2

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](http://dx.doi.org/10.1186%2Fs13015-015-0043-7)).


---

### Answer by username_8 on 2014-03-10. Score: 0

After browsing the [ISGCI](http://www.graphclasses.org/) site I came across the following class: [opposition graphs](http://www.graphclasses.org/classes/gc_89.html).
They seem a possible candidate for your question, but is their obstruction set known?

> **Comments:**
> **username_6**: 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.  
> **username_6**: 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: http://www.informatik.uni-rostock.de/~le/Research/coop.pdf  
> **username_9**: 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.  

---

