...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Order >Interval k-Graphs and Orders
【24h】

Interval k-Graphs and Orders

机译：间隔k图和阶数

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

An interval k-graph is the intersection graph of a family of intervals of the real line partitioned into k classes with vertices adjacent if and only if their corresponding intervals intersect and belong to different classes. In this paper we study the cocomparability interval k-graphs; that is, the interval k-graphs whose complements have a transitive orientation and are therefore the incomparability graphs of strict partial orders. For brevity we call these orders interval k-orders. We characterize the kind of interval representations a cocomparability interval k-graph must have, and identify the structure that guarantees an order is an interval k-order. The case k = 2 is peculiar: cocomparability interval 2-graphs (equivalently proper- or unit-interval bigraphs, bipartite permutation graphs, and complements of proper circular-arc graphs to name a few) have been characterized in many ways, but we show that analogous characterizations do not hold if k 2. We characterize the cocomparability interval 3-graphs via one forbidden subgraph and hence interval 3-orders via one forbidden suborder.
机译：间隔k图是当且仅当它们的相应间隔相交并属于不同类时，实线间隔家族的相交图，该实线间隔被划分为k个类，顶点相邻。在本文中，我们研究了可比区间k-图。就是说，间隔k图的补码具有传递方向，因此是严格偏序的不可比图。为简便起见，我们称这些阶为间隔k阶。我们表征了可比性间隔k图必须具有的间隔表示的种类，并确定保证阶数为间隔k阶的结构。 k = 2的情况是奇特的：可比较间隔2图（等价的固有区间图或单位区间的有向图，二分置换图，以及适当的圆弧图的补全，仅举几例）已被表征，但是我们展示了如果k> 2，类似的表征将不成立。我们通过一个禁止子图来描述可比间隔3图，并因此通过一个禁止子图来描述间隔3阶。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号