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