- Tytuł:
- On a perfect problem
- Autorzy:
- Zverovich, Igor
- Powiązania:
- https://bibliotekanauki.pl/articles/743945.pdf
- Data publikacji:
- 2006
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
hereditary classes
perfect graphs - Opis:
- 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).
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2006, 26, 2; 273-277
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł