Tree- and forest-perfect graphs

DOI10.1016/S0166-218X(99)00071-2MaRDI QIDQ1302153zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Van Bang Le

Publication date 22 September 1999

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

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00071-2

zbMATH Keywords

characterizations of graphsgeneralizations of isomorphismperfect graphs

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17) Structural characterization of families of graphs (05C75)

Review text

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).

Recommendations

• Bipartite-perfect graphs
• Bipartite-perfect graphs
• scientific article; zbMATH DE number 1051283
• Recognition and isomorphism of tree-like \(P_4\)-connected graphs

Cited in

(9)

• Bipartite-perfect graphs
• Graphs with at most two trees in a forest-building process
• Counting spanning trees using modular decomposition
• The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
• Perfect trees and elementary embeddings
• Forests and trees among Gallai graphs
• The use of a pruned modular decomposition for maximum matching algorithms on some graph classes
• Note on Perfect Forests in Digraphs
• Superperfect pairs of trees in graphs

This page was built for publication: Tree- and forest-perfect graphs

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