# Graphclass: bipartite permutation

The following definitions are equivalent:
1. A graph is a bipartite permutation graph, if it is both bipartite and a permutation graph.
2. A strong ordering (<A , <B ) of a bipartite graph G = (A, B, E) consists of an ordering <A of A and an ordering <B of B, such that for all edges ab, a'b', with a,a' in A and b,b' in B: If a <A a' and b <B b', then ab' and a'b are edges.
A bipartite graph is a bipartite permutation graph iff it admits a strong ordering.
Note that there is another definition of a strong ordering in strongly orderable .
3. Let G = (A, B, E) be a bipartite graph. An ordering < of A has the adjacency property, if, for every vertex b in B, N(b) consits of vertices that are consecutive in <. An ordering < of A has the enclosure property, if, for every pair b,b' of vertices in B with N(b) \subseteq N(b'), the vertices of N(b')\N(b) appear consecutively in <, implying that b is adjacent to the leftmost or rightmost neighbour of b' in <.
A bipartite graph G = (A, B, E) is a bipartite permutation graph iff it admits an ordering of A that has the adjacency and enclosure properties.

[+]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

## 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 Linear [+]Details
Domination Linear [+]Details
Feedback vertex set Linear [+]Details
Hamiltonian cycle Linear [+]Details
Hamiltonian path Polynomial [+]Details
Independent set Linear [+]Details
Recognition Linear [+]Details
Treewidth Linear [+]Details
Weighted clique Linear [+]Details
Weighted feedback vertex set Polynomial [+]Details
Weighted independent set Linear [+]Details