Electronic Journal of Graph Theory and Applications (Mar 2015)
A new characterization of trivially perfect graphs
Abstract
A graph $G$ is \emph{trivially perfect} if for every induced subgraph the cardinality of the largest set of pairwise nonadjacent vertices (the stability number) $\alpha(G)$ equals the number of (maximal) cliques $m(G)$. We characterize the trivially perfect graphs in terms of vertex-coloring and we extend some definitions to infinite graphs.
Keywords