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

• perfect graphs, complete coloring, grundy number, forbidden graph characterization