A Freeable Matrix Characterization of Bipartite Graphs of Ferrers Dimension Three

Abstract

Ferrer dimension, along with the order dimension, is a standard dimensional concept for bipartite graphs. In this paper, we prove that a graph is of Ferrer dimension three (equivalent to the intersection bigraph of orthants and points in ${\mathbb{R}}^3$) if and only if it admits a biadjacency matrix representation that does not contain $\Gamma =\left[\begin{array}{ccc}\ast & 1& \ast \\ 1& 0& 1\\ 0& 1& \ast \end{array}\right]$ and $\Delta =\left[\begin{array}{ccc}1& \ast & \ast \\ 0& 1& \ast \\ 1& 0& 1\end{array}\right]$, where $\ast$ denotes zero or one entry.