论文标题
两部分置换图的临界特性
Critical properties of bipartite permutation graphs
论文作者
论文摘要
两部分排列图的类都具有许多不错的重要属性。特别是，该类别在研究集团和排名宽度中至关重要，因为它是无限制和排名宽度的最小遗传图之一。它还包含许多重要的子类，这些子类对于其他参数至关重要，例如图字母或灌木深度，以及其他概念，例如算法问题的良好序或复杂性。在本文中，我们确定了各种类型的两部分置换图的关键子类。
The class of bipartite permutation graphs enjoys many nice and important properties. In particular, this class is critically important in the study of clique- and rank-width of graphs, because it is one of the minimal hereditary classes of graphs of unbounded clique- and rank-width. It also contains a number of important subclasses, which are critical with respect to other parameters, such as graph lettericity or shrub-depth, and with respect to other notions, such as well-quasi-ordering or complexity of algorithmic problems. In the present paper we identify critical subclasses of bipartite permutation graphs of various types.
