Generalized perfect graphs: Characterizations and inversion
type: Item
instance of: scholarly article
title: Generalized perfect graphs: Characterizations and inversion
zbMATH Open document ID: 0833.05064
DOI: 10.1016/0166-218X(94)00066-M
author: Ann Trenk
published in: Discrete Applied Mathematics
publication date: 1996-03-11T00:00:00Z
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.
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 777839
zbMATH Keywords: perfect graphs
zbMATH Keywords: cliques
zbMATH Keywords: subgraph characterizations
zbMATH Keywords: hereditary properties
zbMATH Keywords: SPGC
MaRDI profile type: Publication
cites work: Graphical properties related to minimal imperfection
cites work: Q5422499
cites work: On generalized graph colorings
cites work: Betweenness, orders and interval graphs
cites work: Q4198056
cites work: Q3328583
cites work: Q3216686
cites work: On Partitioning Planar Graphs
cites work: Q4056032
cites work: A characterization of perfect graphs
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Perfect zero–one matrices
cites work: The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
cites work: The validity of the strong perfect-graph conjecture for \((K_4-e)\)-free graphs
cites work: On generalized perfect graphs: Bounded degree and bounded edge perfection
cites work: The Strong Perfect Graph Conjecture for Planar Graphs
full work available at URL: 0166-218x(94)00066-m
OpenAlex ID: W2055939684
description: scientific article; zbMATH DE number 777839