Tree- and forest-perfect graphs (Q1302153)

From MaRDI portal





scientific article; zbMATH DE number 1340632
Language Label Description Also known as
default for all languages
No label defined
    English
    Tree- and forest-perfect graphs
    scientific article; zbMATH DE number 1340632

      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