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
    0 references
    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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references