Bipartite-perfect graphs (Q1811078)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bipartite-perfect graphs |
scientific article |
Statements
Bipartite-perfect graphs (English)
0 references
10 June 2003
0 references
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.
0 references
bipartite graph
0 references
modular decomposition
0 references
perfect graph
0 references
\(P_4\)-structure of graphs
0 references
\(P_4\)-connected graph
0 references
0 references