In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph B = (X,Y,E) in which every cycle of length at least 6 in B has a chord, i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. , p. 261, , Definition 3.4.1, p. 43. A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows.
Characterizations Chordal bipartite graphs have various characterizations in terms of perfect elimination orderings, hypergraphs and matrices. They are closely related to strongly chordal graphs. By definition, chordal bipartite graphs have a forbidden subgraph characterization as the graphs that do not contain any induced cycle of length 3 or of length at least 5 (so-called holes) as an induced subgraph. Thus, a graph G is chordal bipartite if and only if G is triangle-free and hole-free. In , two other characterizations are mentioned: B is chordal bipartite if and only if every minimal edge separator induces a complete bipartite subgraph in B if and only if every induced subgraph is perfect elimination bipartite.
Martin Farber has shown: A graph is strongly chordal if and only if the bipartite incidence graph of its clique hypergraph is chordal bipartite. ; , Theorem 3.4.1, p. 43.
A similar characterization holds for the closed neighborhood hypergraph: A graph is strongly chordal if and only if the bipartite incidence graph of its closed neighborhood hypergraph is chordal bipartite.
Another result found by Elias Dahlhaus is: A bipartite graph B = (X,Y,E) is chordal bipartite if and only if the split graph resulting from making X a clique is strongly chordal., Corollary 8.3.2, p. 129.
A bipartite graph B = (X,Y,E) is chordal bipartite if and only if every induced subgraph of B has a maximum X-neighborhood ordering and a maximum Y-neighborhood ordering.
Various results describe the relationship between chordal bipartite graphs and totally balanced neighborhood hypergraphs of bipartite graphs. , Theorems 8.2.5, 8.2.6, pp. 126–127.
A characterization of chordal bipartite graphs in terms of intersection graphs related to hypergraphs is given in.
A bipartite graph is chordal bipartite if and only if its adjacency matrix is totally balanced if and only if the adjacency matrix is Gamma-free.
Recognition Chordal bipartite graphs can be recognized in time for a graph with n vertices and m edges.; ; ; .
Complexity of problems Various problems such as Hamiltonian cycle, Steiner tree and Efficient Domination remain NP-complete on chordal bipartite graphs.
Various other problems which can be solved efficiently for bipartite graphs can be solved more efficiently for chordal bipartite graphs as discussed in .
Related graph classes Every chordal bipartite graph is a modular graph. The chordal bipartite graphs include the complete bipartite graphs and the bipartite distance-hereditary graphs.Chordal bipartite graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.
Notes
References
. . . . . . . . . . . . . .