Interval bigraphs and circular arc graphs
Interval bigraphs and circular arc graphs
复制标题
区间双图和圆弧图
DOI：
10.1002/jgt.20006
复制
发表时间：
2004
影响因子：
0.9
通讯作者：
Jing Huang
中科院分区：
文献类型：
--
作者：
P. Hell;Jing Huang
证明了区间图的补恰恰是那些覆盖2号团的圆弧图，它们允许没有两条圆弧覆盖整个圆的表示。我们给出了区间图的另一个特征，在顶点排序方面，我们希望这可能有助于找到比目前已知的更有效的识别算法。我们用这些结果证明了在二部图中，几种结构图（固有区间图、固有圆弧图的补、三自由度图、置换图和共可比性图）是相等的。我们的结果证实了Lundgren的一个猜想，并反驳了m<s:1> ller的一个猜想。©2004 Wiley期刊公司[J] .图论学报（自然科学版），2004
We prove that the complements of interval bigraphs are precisely those circular arc graphs of clique covering number two, which admit a representation without two arcs covering the whole circle. We give another characterization of interval bigraphs, in terms of a vertex ordering, that we hope may prove helpful in finding a more efficient recognition algorithm than presently known. We use these results to show equality, amongst bipartite graphs, of several classes of structured graphs (proper interval bigraphs, complements of proper circular arc graphs, asteroidal‐triple‐free graphs, permutation graphs, and co‐comparability graphs). Our results verify a conjecture of Lundgren and disprove a conjecture of Müller. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 313–327, 2004