# On a perfect problem

Discussiones Mathematicae Graph Theory (2006)

- Volume: 26, Issue: 2, page 273-277
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topIgor E. Zverovich. "On a perfect problem." Discussiones Mathematicae Graph Theory 26.2 (2006): 273-277. <http://eudml.org/doc/270312>.

@article{IgorE2006,

abstract = {
We solve Open Problem (xvi) from Perfect Problems of Chvátal [1] available at ftp://dimacs.rutgers.edu/pub/perfect/problems.tex: Is there a class C of perfect graphs such that
(a) C does not include all perfect graphs and
(b) 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).
},

author = {Igor E. Zverovich},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {hereditary classes; perfect graphs},

language = {eng},

number = {2},

pages = {273-277},

title = {On a perfect problem},

url = {http://eudml.org/doc/270312},

volume = {26},

year = {2006},

}

TY - JOUR

AU - Igor E. Zverovich

TI - On a perfect problem

JO - Discussiones Mathematicae Graph Theory

PY - 2006

VL - 26

IS - 2

SP - 273

EP - 277

AB -
We solve Open Problem (xvi) from Perfect Problems of Chvátal [1] available at ftp://dimacs.rutgers.edu/pub/perfect/problems.tex: Is there a class C of perfect graphs such that
(a) C does not include all perfect graphs and
(b) 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).

LA - eng

KW - hereditary classes; perfect graphs

UR - http://eudml.org/doc/270312

ER -

## References

top- [1] V. Chvátal, Perfect Problems, available at http://www.cs.concordia.ca/∼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. Zbl0098.14703
- [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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.