论文标题
树枢轴少量和线性排名
Tree pivot-minors and linear rank-width
论文作者
论文摘要
树宽度及其线性变体路径宽度对于图形次要关系起着核心作用。罗伯逊和西摩（Robertson and Seymour，1983）尤其证明，对于每棵树〜$ t $，不包含$ t $的图形类别作为未成年人的路径宽度。对于枢轴少量关系，从树宽度和路径宽度中接管了等级宽度和线性等级宽度。因此，很自然地检查是否对于每棵树〜$ t $，不包含$ t $的图类类别是枢轴少量的，它们都具有线性排名。我们首先证明，每当$ t $是一棵树不是毛毛虫时，该语句都是错误的。我们猜想，如果$ t $是毛毛虫，则该声明是正确的。我们还能够通过证明：（1）对于每棵树$ t $，$ t $ - p $ - 驾驶的无距离距离远距离式图形的类别具有线性等级宽度，并且仅当$ t $是caterpillar时，我们也能够部分确认此猜想。 （2）对于最多四个顶点的每个毛毛虫$ t $，$ t $ pivot-Minor-Free图的级别都具有线性排名。为了证明我们的第二个结果，我们只需要考虑$ t = p_4 $和$ t = k_ {1,3} $，但是我们遵循一般策略：首先，我们表明，$ t $ -pivot-Minor-Free图中包含在某些类别$ $（H_1，H_1，H_2）$ - 免费的图形中，然后显示为有限的linear linear等级等级。特别是，我们证明了$（k_3，s_ {1,2,2}）$的类$ - 免费图具有有限的线性秩宽，这增强了该图类别具有界限级别宽度的已知结果。
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~$T$, the class of graphs that do not contain $T$ as a minor has bounded path-width. For the pivot-minor relation, rank-width and linear rank-width take over the role from tree-width and path-width. As such, it is natural to examine if for every tree~$T$, the class of graphs that do not contain $T$ as a pivot-minor has bounded linear rank-width. We first prove that this statement is false whenever $T$ is a tree that is not a caterpillar. We conjecture that the statement is true if $T$ is a caterpillar. We are also able to give partial confirmation of this conjecture by proving: (1) for every tree $T$, the class of $T$-pivot-minor-free distance-hereditary graphs has bounded linear rank-width if and only if $T$ is a caterpillar; (2) for every caterpillar $T$ on at most four vertices, the class of $T$-pivot-minor-free graphs has bounded linear rank-width. To prove our second result, we only need to consider $T=P_4$ and $T=K_{1,3}$, but we follow a general strategy: first we show that the class of $T$-pivot-minor-free graphs is contained in some class of $(H_1,H_2)$-free graphs, which we then show to have bounded linear rank-width. In particular, we prove that the class of $(K_3,S_{1,2,2})$-free graphs has bounded linear rank-width, which strengthens a known result that this graph class has bounded rank-width.
