Semi-chordality of digraphs

Jing Huang, Ying Ying Ye

Chordal graphs are important in algorithmic graph theory. Chordal digraphs are a digraph analogue of chordal graphs and have been a subject of active studies recently. In this paper we introduce the notion of semi-strict chordal digraphs which form a class strictly between chordal digraphs and chordal graphs. We characterize semi-strict chordal digraphs by forbidden subdigraphs within the cases of locally semicomplete digraphs and weakly quasi-transitive digraphs.

Knowledge Graph



Sign up or login to leave a comment