Trivially perfect graphs |
| |
| Authors: | Martin Charles Golumbic |
| |
| Institution: | 1. Courant Institute of Mathematical Sciences, New York University, New York, NY, U.S.A.;2. The Weizmann Institute of Science, Rehovot, Israel |
| |
| Abstract: | An undirected graph is trivially perfect if for every induced subgraph the stability number equals the number of (maximal) cliques. We characterize the trivially perfect graphs as a proper subclass of the triangulated graphs (thus disproving a claim of Buneman 3]), and we relate them to some well-known classes of perfect graphs. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
