ArticleOriginal scientific text

Title

On a perfect problem

Authors 1

Affiliations

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

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

Keywords

hereditary classes, perfect graphs

Bibliography

  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.
  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.
Pages:
273-277
Main language of publication
English
Received
2005-09-06
Accepted
2006-03-15
Published
2006
Exact and natural sciences