论文标题
图中的优先级薄度
Precedence thinness in graphs
论文作者
论文摘要
间隔和适当的间隔图是非常著名的图类类，其中有广泛的文献。结果，已经提出了一些间隔图的概括，其中通常以$ k $间隔图表示图表，通过以某种特殊的方式拆分图表。 作为这种方法的最新示例，分别引入了$ k $ thin和适当的$ k $ -thin图的类别的概括间隔和适当的间隔图。即使对于固定的$ k \ geq 2 $，对每个类别的识别的复杂性仍然开放。 在这项工作中，我们引入了一个$ k $ -thin图的子类（分别为$ k $ -thin图），称为优先级$ k $ -thin Graphs（分别为优先级$ k $ -k $ -thin Graphs）。关于分区优先级$ k $ - 薄图，我们提出了一种基于$ pq $ -trees的多项式时间识别算法。关于分区优先级适当的$ k $ -thin图，我们证明，当固定$ k $时，任意$ k $和多项式时间可求解的相关识别问题是\ np complete。此外，我们根据阈值图为这些类别提供了一个表征。
Interval and proper interval graphs are very well-known graph classes, for which there is a wide literature. As a consequence, some generalizations of interval graphs have been proposed, in which graphs in general are expressed in terms of $k$ interval graphs, by splitting the graph in some special way. As a recent example of such an approach, the classes of $k$-thin and proper $k$-thin graphs have been introduced generalizing interval and proper interval graphs, respectively. The complexity of the recognition of each of these classes is still open, even for fixed $k \geq 2$. In this work, we introduce a subclass of $k$-thin graphs (resp. proper $k$-thin graphs), called precedence $k$-thin graphs (resp. precedence proper $k$-thin graphs). Concerning partitioned precedence $k$-thin graphs, we present a polynomial time recognition algorithm based on $PQ$-trees. With respect to partitioned precedence proper $k$-thin graphs, we prove that the related recognition problem is \NP-complete for an arbitrary $k$ and polynomial-time solvable when $k$ is fixed. Moreover, we present a characterization for these classes based on threshold graphs.
