2
$\begingroup$

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.

$\endgroup$
7
  • 7
    $\begingroup$ I'm starting to wonder how many of the "super\d" accounts belong to the same person :P. $\endgroup$
    – R B
    Mar 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$ Mar 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$
    – Juho
    Mar 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$ Mar 8, 2014 at 15:49
  • 2
    $\begingroup$ Is there a motivation for exactly 5 forbidden subgraphs? $\endgroup$ Mar 9, 2014 at 4:08

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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?

$\endgroup$
3
  • 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$
    – JimN
    Mar 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$
    – JimN
    Mar 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$
    – Super8
    Apr 9, 2014 at 20:58

Your Answer

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

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