Chordal bipartite graph

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. ^[1] 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 Golumbic (1980), 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. ^[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.^[4]

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.^[5]

Various results describe the relationship between chordal bipartite graphs and totally balanced neighborhood hypergraphs of bipartite graphs. ^[6]

A characterization of chordal bipartite graphs in terms of intersection graphs related to hypergraphs is given in.^[7]

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. ^[8]

Recognition

Chordal bipartite graphs can be recognized in time O(min(n², (n + m) log n)) for a graph with n vertices and m edges.^[9]

Complexity of problems

Various problems such as Hamiltonian cycle,^[10] Steiner tree ^[11] and Efficient Domination ^[12] 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 ^[13]

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.^[14]

Notes

^ Golumbic (1980), p. 261, Brandstädt, Le & Spinrad (1999), Definition 3.4.1, p. 43.
^ Farber (1983); Brandstädt, Le & Spinrad (1999), Theorem 3.4.1, p. 43.
^ Brandstädt (1991)
^ Brandstädt, Le & Spinrad (1999), Corollary 8.3.2, p. 129.
^ Dragan & Voloshin (1996)
^ Brandstädt, Le & Spinrad (1999), Theorems 8.2.5, 8.2.6, pp. 126–127.
^ Huang (2006)
^ Farber (1983)
^ Lubiw (1987); Paige & Tarjan (1987); Spinrad (1993); Spinrad (2003).
^ Müller (1996)
^ Müller & Brandstädt (1987)
^ Lu & Tang (2002)
^ Spinrad (2003).
^ Chordal bipartite graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.

References

Brandstädt, Andreas (1991), "Classes of bipartite graphs related to chordal graphs", Discrete Applied Mathematics, 32: 51–60, doi:10.1016/0166-218x(91)90023-p.
Brandstädt, Andreas; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Dually Chordal Graphs", SIAM Journal on Discrete Mathematics, 11: 437–455, doi:10.1137/s0895480193253415.
Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
Dragan, Feodor; Voloshin, Vitaly (1996), "Incidence graphs of biacyclic hypergraphs", Discrete Applied Mathematics, 68: 259–266, doi:10.1016/0166-218x(95)00070-8.
Farber, M. (1983), "Characterizations of strongly chordal graphs", Discrete Mathematics, 43 (2–3): 173–189, doi:10.1016/0012-365X(83)90154-1.
Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7.
Huang, Jing (2006), "Representation characterizations of chordal bipartite graphs", Journal of Combinatorial Theory, Series B, 96 (5): 673–683, doi:10.1016/j.jctb.2006.01.001.
Lu, Chin Lung; Tang, Chuan Yi (2002), "Weighted efficient domination on some perfect graphs", Discrete Applied Mathematics, 117: 163–182, doi:10.1016/s0166-218x(01)00184-6.
Lubiw, A. (1987), "Doubly lexical orderings of matrices", SIAM Journal on Computing, 16 (5): 854–879, doi:10.1137/0216057.
Müller, Haiko (1996), "Hamilton circuits in chordal bipartite graphs", Discrete Mathematics, 156: 291–298, doi:10.1016/0012-365x(95)00057-4.
Müller, Haiko; Brandstädt, Andreas (1987), "The NP-completeness of Steiner Tree and Dominating Set for chordal bipartite graphs", Theoretical Computer Science, 53: 257–265, doi:10.1016/0304-3975(87)90067-3.
Paige, R.; Tarjan, R. E. (1987), "Three partition refinement algorithms", SIAM Journal on Computing, 16 (6): 973–989, doi:10.1137/0216062.
Spinrad, Jeremy (1993), "Doubly lexical ordering of dense 0–1 matrices", Information Processing Letters, 45 (2): 229–235, doi:10.1016/0020-0190(93)90209-R.
Spinrad, Jeremy (2003), Efficient Graph Representations, Fields Institute Monographs, American Mathematical Society, ISBN 0-8218-2815-0.

[1] Golumbic (1980), p. 261, Brandstädt, Le & Spinrad (1999), Definition 3.4.1, p. 43.

[2] Farber (1983); Brandstädt, Le & Spinrad (1999), Theorem 3.4.1, p. 43.

[3] Brandstädt (1991)

[4] Brandstädt, Le & Spinrad (1999), Corollary 8.3.2, p. 129.

[5] Dragan & Voloshin (1996)

[6] Brandstädt, Le & Spinrad (1999), Theorems 8.2.5, 8.2.6, pp. 126–127.

[7] Huang (2006)

[8] Farber (1983)

[9] Lubiw (1987); Paige & Tarjan (1987); Spinrad (1993); Spinrad (2003).

[10] Müller (1996)

[11] Müller & Brandstädt (1987)

[12] Lu & Tang (2002)

[13] Spinrad (2003).

[14] Chordal bipartite graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]