In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

area of

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a chordal bipartite graph is a

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

''B'' = (''X'',''Y'',''E'') in which every

cycle Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in so ...

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.

Characterizations

Chordal bipartite graphs have various characterizations in terms of perfect elimination orderings,

hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) ...

s and

matrices Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...

. They are closely related to

strongly chordal graph In the mathematical area of graph theory, an undirected graph is strongly chordal if it is a chordal graph and every cycle of even length (≥ 6) in has an ''odd chord'', i.e., an edge that connects two vertices that are an odd distance (>1) ap ...

s. By definition, chordal bipartite graphs have a forbidden subgraph characterization as the graphs that do not contain any

induced cycle In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an ...

of length 3 or of length at least 5 (so-called holes) as an

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Definit ...

. Thus, a graph ''G'' is chordal bipartite if and only if ''G'' is

triangle-free In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...

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 In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by . A split graph may have m ...

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. A bipartite graph is chordal bipartite if and only if its

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...

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 graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

s and the bipartite

distance-hereditary graph In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any ...

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

Notes

References

*. *. *. *. *. *. *. *. *. *. *. *. *. *. {{refend Graph families Bipartite graphs