ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 26(2) (2006)
Igor E. Zverovich
RUTCOR - Rutgers Center for Operations Research, Rutgers
The State University of New Jersey
640 Bartholomew Road, Piscataway, NJ 08854-8003, USA
Is there a class C of perfect graphs such that
A class P is called locally reducible if there exists a proper
subclass C of P such that every graph in
P contains a local subgraph belonging to C.
We characterize locally reducible hereditary classes. It implies that there
are infinitely many solutions to Open Problem (xvi). However, it is impossible
to find a hereditary class C of perfect graphs satisfying both
(a) and (b).
Keywords: hereditary classes, perfect graphs.
2000 Mathematics Subject Classification: 05C17 (Perfect graphs).
Received 6 September 2005
Revised 15 March 2006