Strongly chordal digraphs and $Γ$-free matrices

Pavol Hell, Cesar Hernandez-Cruz, Jing Huang, Jephian C. -H. Lin

Published 2019-09-09Version 1

We define strongly chordal digraphs, which generalize strongly chordal graphs and chordal bipartite graphs, and are included in the class of chordal digraphs. They correspond to square 0,1 matrices that admit a simultaneous row and column permutation avoiding the {\Gamma} matrix. In general, it is not clear if these digraphs can be recognized in polynomial time, and we focus on symmetric digraphs (i.e., graphs with possible loops), tournaments with possible loops, and balanced digraphs. In each of these cases we give a polynomial-time recognition algorithm and a forbidden induced subgraph characterization.