DIMACS TR: 2003-12
Basic perfect graphs and their extensions
Authors: I. E. Zverovich and V. E. Zverovich
ABSTRACT
We characterize basic graphs introduced
by Chudnovsky, Robertson, Seymour, and Thomas \cite{ChudnovskyRST}
in terms of forbidden induced subgraphs.
%The {\em GraphLab} software package \cite{Zverovich-GraphLab}
%was used in our research.
Then we apply Reducing Pseudopath Method of Zverovich
\cite{ZverovichRRR14-2001} to find forbidden induced subgraphs
the substitutional closure of the class of basic graphs, thus
obtaining a characterization of a hereditary subclass of
perfect graphs.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-12.ps.gz
DIMACS Home Page