Generalized perfect graphs: Characterizations and inversion

DOI10.1016/0166-218X(94)00066-MMaRDI QIDQ1894378zbMATH OpenOpenAlexFDO

Publication date 11 March 1996

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(94)00066-m

cliques hereditary properties perfect graphs SPGC subgraph characterizations

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Review text

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.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Generalized perfect graphs: Characterizations and inversion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1894378)