PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2006 | 26 | 2 | 273-277
Tytuł artykułu

On a perfect problem

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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).
Słowa kluczowe
Kategorie tematyczne
Wydawca
Rocznik
Tom
26
Numer
2
Strony
273-277
Opis fizyczny
Daty
wydano
2006
otrzymano
2005-09-06
poprawiono
2006-03-15
Twórcy
  • RUTCOR - Rutgers Center for Operations Research, Rutgers, The State University of New Jersey, 640 Bartholomew Road, Piscataway, NJ 08854-8003, USA
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1318
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.