DIMACS TR: 2003-36

A solution to a problem of Le



Authors: I. E. Zverovich

ABSTRACT
Let $S_1, S_2, \ldots , S_t$ be pairwise disjoint non-empty stable sets in a graph $H$. The graph $H^*$ is obtained from $H$ by replacing each $S_i$ by a new vertex $q_i$,

joining each $q_i$ and $q_j$, $1 \le i \neq j \le t$, and

joining $q_i$ to all vertices in $H - (S_1 \cup S_2 \cup\cdots \cup S_t)$ which were adjacent to some vertex of $S_i$.

A \em{cograph} is a $P_4$-free graph. A graph $G$ is called a {\em cograph contraction} if there exist a cograph $H$ and pairwise disjoint non-empty stable sets in $H$ for which $G \simeq H^*$. Solving a problem proposed by Le~\cite{Le99}, we give a finite forbidden induced subgraph characterization of cograph contractions.

{\bf Keywords:} {Cograph contractions, perfect graphs,weakly chordal graphs, forbidden induced subgraphs}.

{\bf 2000 Mathematics Subject Classification:} 05C17

Paper available at ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-36.ps.gz

DIMACS Home Page