DIMACS TR: 2003-12

Basic perfect graphs and their extensions

Authors: I. E. Zverovich and V. E. Zverovich


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