On generalized perfect graphs: Bounded degree and bounded edge perfection (Q686267): Difference between revisions

Let \({\mathcal P}\) be a hereditary family of graphs. The \({\mathcal P}\)-chromatic number of \(G\), \(\chi_{\mathcal P}\), is the minimum size of a vertex partition such that each part induces a subgraph in \({\mathcal P}\). If \({\mathcal P}\) is the family of edgeless graphs, then \(\chi_{\mathcal P}\) is the usual chromatic number. Define \(\omega_{\mathcal P}(G)\) to be \(\chi_{\mathcal P}(K)\) where \(K\) is the largest clique in \(G\). Define \(G\) to be \(\chi_{\mathcal P}\)-perfect if \(\chi_{\mathcal P}(H)=\omega_{\mathcal P}(H)\) for all induced subgraphs \(H\) of \(G\). The authors examine analogs of the Perfect Graph Conjecture (PGC) and the Strong Perfect Graph Conjecture (SPGC) for various heriditary families \({\mathcal P}\). The PGC says that a graph is \(\chi_{\mathcal P}\)-perfect if and only if its complement is \(\chi_{\mathcal P}\)-perfect. The SPGC says that \(G\) is \(\chi_{\mathcal P}\)-perfect if and only if neither \(G\) nor its complement contains an induced odd cycle of length five or greater. The PGC is true for the usual chromatic number, but there are heriditary families for which it is false. The authors prove the PGC and the SPGC for the properties ``has at most \(t\) edges'', and ``has maximum degree at most \(t\)'' for \(t>0\).