Premium
A good characterization of cograph contractions
Author(s) -
Le Van Bang
Publication year - 1999
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/(sici)1097-0118(199904)30:4<309::aid-jgt5>3.0.co;2-5
Subject(s) - cograph , combinatorics , mathematics , pairwise comparison , graph , characterization (materials science) , disjoint sets , discrete mathematics , pathwidth , line graph , statistics , materials science , nanotechnology
A graph is called a graph 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 split graphs. This article gives a good characterization of cograph contractions, solving a problem posed by M. Hujter and Zs. Tuza. © John Wiley & Sons, Inc. J Graph Theory 30: 309–318, 1999