𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Forbidden induced subgraph characterization of cograph contractions

✍ Scribed by Igor Ed. Zverovich; Inessa I. Zverovich

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
101 KB
Volume
46
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Let S 1 ; S 2 ; . . . ; S t be pairwise disjoint non-empty stable sets in a graph H. The graph H Γƒ is obtained from H by: (i) replacing each S i by a new vertex q i ; (ii) joining each q i and q j , 1 i 6 ΒΌ j t, and; (iii) joining q i to all vertices in HΓ€(S 1 [ S 2 [ Á Á Á [ S t ) which were adjacent to some vertex of S i . A cograph is a P 4 -free graph. A graph G is called a cograph contraction if there exist a cograph H and pairwise disjoint non-empty stable sets in H for which G ' H Γƒ . Solving a problem proposed by Le [2], we give a finite forbidden induced subgraph characterization of cograph contractions.

πŸ“œ SIMILAR VOLUMES

A good characterization of cograph contr
A good characterization of cograph contractions
✍ Le, Van Bang πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 127 KB

A graph is called a cograph contraction if it is obtained from a cograph (a graph with no induced path on four vertices) by contracting some pairwise disjoint independent sets and then making the ''contracted'' vertices pairwise adjacent. Cograph contractions are perfect and generalize cographs and

Characterizing path graphs by forbidden
Characterizing path graphs by forbidden induced subgraphs
✍ Benjamin LΓ©vΓͺque; FrΓ©dΓ©ric Maffray; Myriam Preissmann πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 197 KB

## Abstract A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property. Β© 2009

A semi-induced subgraph characterization
A semi-induced subgraph characterization of upper domination perfect graphs
✍ Zverovich, Igor E.; Zverovich, Vadim E. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 324 KB πŸ‘ 2 views

Let Ξ²(G) and Ξ“(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Ξ“-perfect if Ξ²(H) = Ξ“(H), for every induced subgraph H of G. The class of Ξ“-perfect graphs generalizes such well-known classes of graphs as strongly perfect graphs, absorbantl