Chordal bipartite graph

Chordal bipartite graphs have various characterizations in terms of perfect elimination orderings, hypergraphs and matrices.

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.

[2] 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.

[3] 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.

[9] Various problems such as Hamiltonian cycle,[10] Steiner tree [11] and Efficient Domination [12] remain NP-complete on chordal bipartite graphs.

Every cycle of length at least 6 has a chord connecting two vertices that are a distance > 1 apart from each other in the cycle.