Tree- and forest-perfect graphs (Q1302153)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Tree- and forest-perfect graphs |
scientific article |
Statements
Tree- and forest-perfect graphs (English)
0 references
22 September 1999
0 references
Let graphs \(G\) and \(H\) have the same vertex set \(V\). \(G\) and \(H\) are \(P_4\)-isomorphic if there is a permutation \(\pi\) on \(V\) such that, for every \(W\subseteq V\), \(G[W]\cong P_4\) if and only if \(H[W]\cong P_4\), where \(G[W]\), \(H[W]\) are the subgraphs of \(G\), \(H\) induced by \(W\). This paper gives a classification of all graphs \(P_4\)-isomorphic to a tree (a forest, respectively).
0 references
characterizations of graphs
0 references
perfect graphs
0 references
generalizations of isomorphism
0 references