Preperfect graphs |
| |
| Authors: | Peter L. Hammer Frédéric Maffray |
| |
| Affiliation: | (1) RUTCOR, Rutgers Center for Operations Research Hill Center, Busch Campus, Rutgers University, 08 903 New Brunswick, NJ, U.S.A.;(2) LSD2-IMAG, C.N.R.S., BP 53 X, 38041 Grenoble Cedex, France |
| |
| Abstract: | We say that a vertexx of a graph is predominant if there exists another vertexy ofG such that either every maximum clique ofG containingy containsx or every maximum stable set containingx containsy. A graph is then called preperfect if every induced subgraph has a predominant vertex. We show that preperfect graphs are perfect, and that several well-known classes of perfect graphs are preperfect. We also derive a new characterization of perfect graphs. |
| |
| Keywords: | 05 C 15 05 C 70 05 C 75 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
