Chordal bipartite graph

In graph theory , a finite graph G is called chordal bipartite (English chordal bipartite ) if every induced circle in G has exactly length 4. Some NP-hard problems can be solved efficiently on this graph class .

Definitions

A bipartite graph with bipartite decomposition is called chordal bipartite if it fulfills one (and therefore all) of the following equivalent definitions: ${\ displaystyle G = (V, E)}$ ${\ displaystyle V = A \ cup B}$

every circle of length at least 6 has a chord, d. H. there is an edge in the graph between two nodes that are not adjacent in the circle.

the graph resulting from adding all the edges between nodes in is strongly chordal . ${\ displaystyle G}$ ${\ displaystyle A}$

there is an arrangement of the edges such that (for the sequence defined by) the union of the neighborhoods of the two nodes of is a completely bipartite subgraph in , i.e. H. each node in is connected to each node in by an edge in . ${\ displaystyle G_ {0} = G, G_ {i} = G_ {i-1} -e_ {i}}$ ${\ displaystyle e_ {i} = \ left \ {x_ {i}, y_ {i} \ right \}}$ ${\ displaystyle G_ {i-1}}$ ${\ displaystyle N (x_ {i})}$ ${\ displaystyle N (y_ {i})}$ ${\ displaystyle G_ {i-1}}$

Note that chordal bipartite graphs do not have to be chordal . The term weakly chordal bipartite would actually be more precise , since these graphs are weakly chordal and bipartite , on the other hand there is no risk of confusion, since circles in bipartite graphs must always have an even length.

A graph is strongly chordal if and only if its associated bipartite graph is chordal bipartite.

literature

Mihály Bakonyi, Aaron Bono: Several Results on Chordal Bipartite Graphs . Czechoslovak Mathematical Journal, Volume 47 - Number 4 - December 1997, ISSN 0011-4642 , pp. 577-583 PDF
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 .
Jorge L. Ramírez Alfonsín, Bruce A. Reed: Perfect Graphs . Wiley 2001, ISBN 9780471489702 , p. 141 ( limited online version in Google Book Search - USA )
Golumbic, Martin Charles; Goss, Clinton F .: Perfect elimination and chordal bipartite graphs. J. Graph Theory 2 (1978), no. 2, 155-163. PDF

Web links

chordal bipartite - Entry in the Information System on Graph Classes and their Inclusions

Individual evidence

↑ Theorem 2.3 in: Brandstädt, Andreas: Classes of bipartite graphs related to chordal graphs. Discrete Applied Mathematics 32 (1991) 51-60

[1] Theorem 2.3 in: Brandstädt, Andreas: Classes of bipartite graphs related to chordal graphs. Discrete Applied Mathematics 32 (1991) 51-60