A new characterization of trivially perfect graphs

Christian Rubio Montiel


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.


Perfect graphs, complete coloring, Grundy number, forbidden graph characterization

Full Text:


DOI: http://dx.doi.org/10.5614/ejgta.2015.3.1.3


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats