# Graphclass: chordal bipartite

The following definitions are equivalent:
1. A bipartite graph is chordal bipartite if each cycle of length at least 6 has a chord.
2. Let $G=(X,Y,E)$ be a bipartite graph. An edge $(x,y)$ is called bisimplicial if $N(x)\cup N(y)$ induces a complete bipartite graph in $G$.
Let $(e_1,\dots,e_m)$ be an ordering of the edges of $G$. Let $G_0=G$ and $G_i = G_{i-1} \setminus e_i$ ($G_i$ is obtained from $G_{i-1}$ by removing the edge $e_i$ but not its endvertices). The ordering $(e_1,\dots,e_m)$ is a perfect edge-without-vertex elimination ordering if $e_i$ is bisimplicial in $G_{i-1}$ for all $1\le i\le m$.
A bipartite graph is chordal bipartite if it admits a perfect edge-without-vertex elimination ordering.
3. Let $G=(X,Y,E)$ be a bipartite graph. Let $G'$ be the graph obtained from $G$ by adding an edge between every pair of vertices in $X$. A bipartite graph $G$ is chordal bipartite if $G'$ is strongly chordal .

Note these are not chordal because induced C4 s are allowed. The name bipartite ∩ weakly chordal is clearer.

[457]

[+]Details

## Inclusions

The map shows the inclusions between the current class and a fixed set of landmark classes. Minimal/maximal is with respect to the contents of ISGCI. Only references for direct inclusions are given. Where no reference is given, check equivalent classes or use the Java application. To check relations other than inclusion (e.g. disjointness) use the Java application, as well.

[+]Details

[+]Details

[+]Details

## Problems

3-Colourability Linear [+]Details
Clique Linear [+]Details
Clique cover Polynomial [+]Details
Cliquewidth Unbounded [+]Details
Cliquewidth expression Unbounded or NP-complete [+]Details
Colourability Linear [+]Details
Cutwidth Unknown to ISGCI [+]Details
Domination NP-complete [+]Details
Feedback vertex set Polynomial [+]Details
Hamiltonian cycle NP-complete [+]Details
Hamiltonian path NP-complete [+]Details
Independent set Polynomial [+]Details
Recognition Polynomial [+]Details
Treewidth Polynomial [+]Details
Weighted clique Linear [+]Details
Weighted feedback vertex set Unknown to ISGCI [+]Details
Weighted independent set Polynomial [+]Details