Representation characterizations of chordal bipartite graphs

详细信息    查看全文

• 作者：Jing Huang
• 关键词：Chordal bipartite graph ; Strongly chordal graph ; Ferrers dimension ; Interval bigraph ; Circular arc graph ; Characterization
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2006
• 出版时间：September 2006
• 年：2006
• 卷：96
• 期：5
• 页码：673-683
• 全文大小：138 K

文摘

A bipartite graph is chordal bipartite if it does not contain an induced cycle of length at least six. We give three representation characterizations of chordal bipartite graphs. More precisely, we show that a bipartite graph is chordal bipartite if and only if the complement is the intersection graph of a family of pairwise compatible claws in a weighted hypercircle. (A hypercircle is a graph which consists of internally vertex disjoint paths between two distinguished vertices, and a claw in a hypercircle is a connected subgraph containing exactly one of the two distinguished vertices.) We also introduce two classes of bipartite graphs, both containing interval bigraphs and interval containment bigraphs. They are compatible subtree intersection bigraphs and compatible subtree containment bigraphs. We show that these two classes are identical to the class of chordal bipartite graphs.