A new characterization of trivially perfect graphs
| Main Author: | Montiel, Christian Rubio; National Autonomous University of Mexico |
|---|---|
| Other Authors: | CONACyT of Mexico grant 166306 and 178395 |
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2015
|
| Subjects: | |
| Online Access: |
http://www.ejgta.org/index.php/ejgta/article/view/60 http://www.ejgta.org/index.php/ejgta/article/view/60/31 |
Daftar Isi:
- 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.