Generalized perfect graphs: Characterizations and inversion (Q1894378): Difference between revisions

The author generalizes the notion of perfect graphs as follows: Let \(\mathcal P\) be a hereditary family of graphs. Then \(\chi_{\mathcal P}(G)\), the \({\mathcal P}\)-chromatic number of the graph \(G\) is the minimum integer such that \(V(G)\) has a partition \(V_1\cup V_2\cup\cdots \cup V_k\) with each induced subgraph \(G[V_i]\) a member of \(\mathcal P\). The \(\max\{\chi_{\mathcal P}(K)\}\) over all cliques of \(G\) is defined to be the \({\mathcal P}\)-clique number \(\omega_{\mathcal P}(G)\), and \(G\) is said to be \(\chi_{\mathcal P}\)-perfect if \(\chi_{\mathcal P}(H)= \omega_{\mathcal P}(H)\) for all induced subgraphs \(H\) of \(G\). The set of all \(\chi_{\mathcal P}\)- perfect graphs is denoted by \({\mathcal P}^*\). In the first part of the paper the author `gives' forbidden subgraph characterizations of \({\mathcal P}^*\) for several families \(\mathcal P\), citing her dissertation for most of the proofs, for example, for \({\mathcal P}=\) \{acyclic graphs\}, \({\mathcal P}^*= \) \{chordal graphs\}. A two-step procedure is indicated to get \({\mathcal P}^*\) for any \(\mathcal P\). The second step involves finding \(\{\text{Free}(K^*_n)\}\) for integers \(n\geq 2\), where for a family \(\mathcal F\) of graphs, \(\text{Free}({\mathcal F})\) is the set of all graphs \(G\) which do not have any member of \(\mathcal F\) as an induced subgraph. The author reports only partial success in this. In the latter part of the paper the author starts from the observation that the mapping \({\mathcal P}\to {\mathcal P}^*\) is not one-to-one and tackless the `inversion problem' of finding all hereditary properties \(\mathcal P\) for which \({\mathcal P}^*= {\mathcal Q}\) a given hereditary family. Several interesting results are proved and many open problems are suggested in the concluding section. Finally, it is amusingly demonstrated that all these ingenious methods leave the SPGC where it is: still a conjecture.