Partitions of graphs into one or two independent sets and cliques : Revised version

Brandstädt, Andreas

lt is shown that it can be recognized in polynomial time whether the vertex set of a finite undirected graph can be partitioned into one or two independent sets and cliques. Such graphs generalize bipartite and split graphs and the result also shows that it can be recognized in polynomial time whether a graph can be partitioned into two split graphs. An efficient time bound 0(n2m) is given for the recognition of graphs which can be partitioned into two independent sets and one clique.

Vorschau

Zitieren

Zitierform:

Brandstädt, Andreas: Partitions of graphs into one or two independent sets and cliques. Revised version. Hagen 1991. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe