ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2021): 1.028

5-year Journal Impact Factor (2021): 0.934

CiteScore (2021): 1.7

SNIP (2021): 1.157

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 26(2) (2006) 273-277


Igor E. Zverovich

RUTCOR - Rutgers Center for Operations Research, Rutgers
The State University of New Jersey
640 Bartholomew Road, Piscataway, NJ 08854-8003, USA


We solve Open Problem (xvi) from Perfect Problems of Chvátal [1] available at

Is there a class C of perfect graphs such that

C does not include all perfect graphs and
every perfect graph contains a vertex whose neighbors induce a subgraph that belongs to C?

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).


[1] V. Chvátal, Perfect Problems, available at∼chvatal/perfect/problems.html
[2] G.A. Dirac, On rigid circuit graphs, Abh. Math. Semin. Univ. Hamburg 25 (1961) 71-76, doi: 10.1007/BF02992776.
[3] Perfect graphs, Edited by J.L. Ramírez Alfonsín and B.A. Reed, Wiley-Interscience Series in Discrete Mathematics and Optimization (John Wiley & Sons, Ltd., Chichester, 2001) xxii+362 pp.
[4] A.A. Zykov, Fundamentals of Graph Theory (Nauka, Moscow, 1987) 382 pp. (in Russian), translated and edited by L. Boron, C. Christenson and B. Smith (BCS Associates, Moscow, ID, 1990) vi+365 pp.

Received 6 September 2005
Revised 15 March 2006