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.
$\begingroup$
$\endgroup$
7
-
7$\begingroup$ I'm starting to wonder how many of the "super\d" accounts belong to the same person :P. $\endgroup$– R BMar 8, 2014 at 9:56
-
2$\begingroup$ 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 $\endgroup$– Tyson WilliamsMar 8, 2014 at 10:41
-
$\begingroup$ Just have a look here; you can then decide for yourself what exactly you consider natural out of them, if any :-) $\endgroup$– JuhoMar 8, 2014 at 13:01
-
5$\begingroup$ @Super3 it is easier to participate on the site if you register an account. We can then merge your 4 other accounts with it. $\endgroup$– Artem Kaznatcheev ♦Mar 8, 2014 at 15:49
-
2$\begingroup$ Is there a motivation for exactly 5 forbidden subgraphs? $\endgroup$– Vinicius dos SantosMar 9, 2014 at 4:08
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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).
$\begingroup$
$\endgroup$
3
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?
-
2$\begingroup$ 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. $\endgroup$– JimNMar 10, 2014 at 16:50
-
3$\begingroup$ 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 $\endgroup$– JimNMar 10, 2014 at 16:58
-
$\begingroup$ 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. $\endgroup$– Super8Apr 9, 2014 at 20:58