Forbidden induced subgraph characterization of cograph contractions | Zendy

Zverovich Igor Ed. | Zendy; Zverovich Inessa I. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Forbidden induced subgraph characterization of cograph contractions

Author(s) -

Zverovich Igor Ed.,

Zverovich Inessa I.

Publication year - 2004

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.20002

Subject(s) - combinatorics , cograph , induced subgraph , mathematics , vertex (graph theory) , disjoint sets , pairwise comparison , graph , discrete mathematics , characterization (materials science) , line graph , pathwidth , physics , statistics , optics

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 # 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. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 217–226, 2004

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research