𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Partition the vertices of a graph into one independent set and one acyclic set

✍ Scribed by Aifeng Yang; Jinjiang Yuan

Book ID
108113570
Publisher
Elsevier Science
Year
2006
Tongue
English
Weight
264 KB
Volume
306
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Partitions of graphs into one or two ind
Partitions of graphs into one or two independent sets and cliques
✍ Andreas BrandstΓ€dt πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 417 KB

It is shown in this note 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 one or two cliques. Such graphs generalize bipartite and split graphs and the result also shows that it can be recognized

Constraints on the number of maximal ind
Constraints on the number of maximal independent sets in graphs
✍ Jiuqiang Liu πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 387 KB πŸ‘ 2 views

## Abstract A maximal independent set of a graph __G__ is an independent set that is not contained properly in any other independent set of __G__. Let __i(G)__ denote the number of maximal independent sets of __G__. Here, we prove two conjectures, suggested by P. ErdΓΆs, that the maximum number of m