Comparability and Cocomparability Bigraphs

Jephian C.-H. Lin

Department of Applied Mathematics

National Sun Yat-sen University

chlin@math.nsysu.edu.tw

    Let `\mathcal{F}` be a family `0,1`-matrix. A `0,1`-matrix `M` is symmetrically `\mathcal{F}`-free if there is a permutation matrix `P` such that `P^\top MP` does not contain any `S\in\mathcal{F}` as a submatrix. For a given graph `G`, the neighborhood matrix of `G` is defined as `A(G)+I`, where `A(G)` is the adjacency matrix and `I` is the identity matrix. Several important graph classes are known to have a characterization from the matrix point of view. For example, let \[\Gamma=\begin{bmatrix}1&1\\1&0\end{bmatrix}\text{ and }\texttt{slash}=\begin{bmatrix}0&1\\1&0\end{bmatrix}.\] Thus, the strongly chordal graphs are the graphs whose neighborhood matrix is symmetrically `\{\Gamma\}`-free; the cocomparability graphs are the graphs whose neighborhood matrix can be permuted to avoid `tt"slash"` on the main diagonal; and the interval graphs are the graphs whose neighborhood matrix is symmetrically `\{\Gamma,\mathtt{slash}\}`-free. Note that the set of interval graphs is the intersection of the set of strongly chordal graphs and the set of cocomparability graphs. There are bipartite analogues for the strongly chordal graphs and the interval graphs, namely, the bipartite chordal graphs and the interval containment graphs. In this talk, we introduce the cocomparability bigraphs from the matrix perspective as a bipartite analogue to the cocomparability graphs.
This is a joint work with Pavol Hell, Jing Huang, and Ross M. McConnell.

Keyword: submatrix avoiding, comparability graph, bigraph