Bipartite-perfect graphs

DOI10.1016/S0166-218X(02)00390-6MaRDI QIDQ1811078zbMATH OpenFDO

Authors Van Bang Le

Publication date 10 June 2003

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

Full work available at URL https://doi.org/10.1016/S0166-218X(02)00390-6

zbMATH Keywords

\(P_4\)-connected graph\(P_4\)-structure of graphsbipartite graphmodular decompositionperfect graph

Mathematics Subject Classification ID

Perfect graphs (05C17)

Review text

Two graphs \(G\) and \(H\) on the vertex set \(V\) are \(P_4\)-isomorphic if there is a permutation \(\pi\) on \(V\) such that, for all subsets \(S\) of \(V\), \(S\) induces a chordless \(P_4\) in \(G\) if and only if \(\pi (S)\) induces a \(P_4\) in \(H\). The author characterizes all graphs \(P_4\)-isomorphic to a bipartite graph. For example, we can derive from such a graph or its complement a bipartite graph, or a tree-perfect graph, or two particular graphs on 7 and 8 vertices. The proof requires an exhaustive examination of the possible neighbors of the vertices in known cycles.

Recommendations

• Bipartite-perfect graphs
• scientific article; zbMATH DE number 1555974
• Bipartite permutation graphs
• Bipartite bithreshold graphs
• scientific article; zbMATH DE number 3987
• Perfect matchings of regular bipartite graphs
• Bipartable graphs
• Bipartite Graphs and their Degree Sets
• scientific article; zbMATH DE number 165141
• scientific article; zbMATH DE number 1796985

Cites work

• A Linear Recognition Algorithm for Cographs
• A semi-strong perfect graph theorem
• Efficiently recognizing the P₄-structure of trees and of bipartite graphs without short cycles
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3887731 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1753165 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• Modular decomposition and transitive orientation
• P-Components and the Homogeneous Decomposition of Graphs
• Recognizing the \(P_ 4\)-structures of a tree
• Recognizing the \(P_4\)-structure of bipartite graphs
• Recognizing the \(P_4\)-structure of block graphs
• Split-Perfect Graphs: Characterizations and Algorithmic Use
• Topics on perfect graphs
• Tree- and forest-perfect graphs

Cited in

(9)

• A notion of cross-perfect bipartite graphs
• Bipartable graphs
• Tree- and forest-perfect graphs
• Nearly bipartite graphs
• On edge perfectness and classes of bipartite graphs
• Bipartite finite Toeplitz graphs
• Bipartite-perfect graphs
• scientific article; zbMATH DE number 726921 (Why is no real title available?)
• scientific article; zbMATH DE number 1555974 (Why is no real title available?)

This page was built for publication: Bipartite-perfect graphs

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