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. Unlike chordal graphs, chordal digraphs lack many structural properties such as forbidden subdigraph or representation characterizations. In this paper we introduce the notion of semi-strict chordal digraphs which form a class strictly between chordal digraphs and chordal graphs. Semi-strict chordal digraphs have rich structural properties. We characterize semi-strict chordal digraphs in terms of knotting graphs, a notion analogous to the one introduced by Gallai for the study of comparability graphs. We also give forbidden subdigraph characterizations of semi-strict chordal digraphs within the cases of locally semicomplete digraphs and weakly quasi-transitive digraphs.
翻译:弦形图在算法图学理论中很重要。 弦形图是chordal 图形的比喻类比,是最近积极研究的主题。 与chordal 图形不同, 堂形图与chordal 图形不同, 堂状图缺乏许多结构属性, 例如被禁止的子体或描述特征。 在本文中, 我们引入了半管形图概念, 严格地在光谱和chordal 图形之间形成一个等级。 半管形图具有丰富的结构特性。 我们用结结结图来描述半管形图, 这一概念类似于加莱为比较图研究而提出的概念。 我们还在本地半成图和薄弱的准转成图中, 对半管形图作了被禁止的子体特征描述。