Chordal bipartite graph

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 {{harvtxt|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.

{{harvtxt|Farber|1983}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, 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.{{harvtxt|Brandstädt|1991}}

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.{{harvtxt|Brandstädt|Le|Spinrad|1999}}, 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.{{harvtxt|Dragan|Voloshin|1996}}

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

{{harvtxt|Brandstädt|Le|Spinrad|1999}}, 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.{{harvtxt|Huang|2006}}

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.

{{harvtxt|Farber|1983}}

Chordal bipartite graphs can be recognized in time {{nowrap|O(min(n², (n + m) log n))}} for a graph with n vertices and

m edges.{{harvtxt|Lubiw|1987}}; {{harvtxt|Paige|Tarjan|1987}}; {{harvtxt|Spinrad|1993}}; {{harvtxt|Spinrad|2003}}.

Various problems such as Hamiltonian cycle,{{harvtxt|Müller|1996}} Steiner tree {{harvtxt|Müller|Brandstädt|1987}} and Efficient Domination

{{harvtxt|Lu|Tang|2002}} 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

{{harvtxt|Spinrad|2003}}.

Every chordal bipartite graph is a modular graph. The chordal bipartite graphs include the complete bipartite graphs and the bipartite distance-hereditary graphs.[http://www.graphclasses.org/classes/gc_79.html Chordal bipartite graphs], Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.

{{reflist|30em}}

{{refbegin|30em}}

• {{citation

| last = Brandstädt | first = Andreas | authorlink = Andreas Brandstädt

| title = Classes of bipartite graphs related to chordal graphs

| journal = Discrete Applied Mathematics

| volume = 32

| pages = 51–60

| year = 1991

| doi=10.1016/0166-218x(91)90023-p| doi-access = free

}}.

• {{citation

| last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt

| last2 = Dragan | first2 = Feodor

| last3 = Chepoi | first3 = Victor

| last4 = Voloshin | first4 = Vitaly

| title = Dually Chordal Graphs

| journal = SIAM Journal on Discrete Mathematics

| volume = 11

| pages = 437–455

| year = 1998 | doi=10.1137/s0895480193253415}}.

• {{citation

| last1 = Brandstädt

| first1 = Andreas

| author1-link = Andreas Brandstädt

| last2 = Le

| first2 = Van Bang

| last3 = Spinrad

| first3 = Jeremy

| title = Graph Classes: A Survey

| publisher = SIAM Monographs on Discrete Mathematics and Applications

| year = 1999

| isbn = 0-89871-432-X

| url-access = registration

| url = https://archive.org/details/graphclassessurv0000bran

}}.

• {{citation

| last1 = Dragan | first1 = Feodor

| last2 = Voloshin | first2 = Vitaly

| title = Incidence graphs of biacyclic hypergraphs

| journal = Discrete Applied Mathematics

| volume = 68

| pages = 259–266

| year = 1996

| doi=10.1016/0166-218x(95)00070-8| doi-access =

}}.

• {{citation

| last = Farber | first = M.

| doi = 10.1016/0012-365X(83)90154-1

| issue = 2–3

| journal = Discrete Mathematics

| pages = 173–189

| title = Characterizations of strongly chordal graphs

| volume = 43

| year = 1983| doi-access =

}}.

• {{citation

| last = Golumbic | first = Martin Charles

| title = Algorithmic Graph Theory and Perfect Graphs

| publisher = Academic Press

| year = 1980

| isbn = 0-12-289260-7}}.

• {{citation

| last = Huang | first = Jing

| doi = 10.1016/j.jctb.2006.01.001

| journal = Journal of Combinatorial Theory, Series B

| pages = 673–683

| title = Representation characterizations of chordal bipartite graphs

| volume = 96

| issue = 5

| year = 2006| doi-access = free

}}.

• {{citation

| last1 = Lu | first1 = Chin Lung

| last2 = Tang | first2 = Chuan Yi

| title = Weighted efficient domination on some perfect graphs

| journal = Discrete Applied Mathematics

| volume = 117

| pages = 163–182

| year = 2002

| doi=10.1016/s0166-218x(01)00184-6| doi-access = free

}}.

• {{citation

| last = Lubiw | first = A. | authorlink = Anna Lubiw

| doi = 10.1137/0216057

| issue = 5

| journal = SIAM Journal on Computing

| pages = 854–879

| title = Doubly lexical orderings of matrices

| volume = 16

| year = 1987}}.

• {{citation

| last = Müller | first = Haiko

| title = Hamilton circuits in chordal bipartite graphs

| journal = Discrete Mathematics

| volume = 156

| pages = 291–298

| year = 1996

| doi=10.1016/0012-365x(95)00057-4| doi-access = free

}}.

• {{citation

| last1 = Müller | first1 = Haiko

| last2 = Brandstädt | first2 = Andreas | author2-link = Andreas Brandstädt

| title = The NP-completeness of Steiner Tree and Dominating Set for chordal bipartite graphs

| journal = Theoretical Computer Science

| volume = 53

| pages = 257–265

| year = 1987

| doi=10.1016/0304-3975(87)90067-3| doi-access = free

}}.

• {{citation

| last1 = Paige | first1 = R.

| last2 = Tarjan | first2 = R. E. | author2-link = Robert Tarjan

| doi = 10.1137/0216062

| issue = 6

| journal = SIAM Journal on Computing

| pages = 973–989

| title = Three partition refinement algorithms

| volume = 16| year = 1987

}}.

• {{citation

| last = Spinrad | first = Jeremy

| doi = 10.1016/0020-0190(93)90209-R

| issue = 2

| journal = Information Processing Letters

| pages = 229–235

| title = Doubly lexical ordering of dense 0–1 matrices

| volume = 45

| year = 1993}}.

• {{citation

| last = Spinrad | first = Jeremy

| title = Efficient Graph Representations

| publisher = Fields Institute Monographs, American Mathematical Society

| year = 2003

| isbn = 0-8218-2815-0}}.

{{refend}}

Category:Graph families

Category:Bipartite graphs