Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Chordal bipartite graph
Summary
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.
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.
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.
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.
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.
A characterization of chordal bipartite graphs in terms of intersection graphs related to hypergraphs is given in.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.