论文标题
带有无界灌木的图形类中的换长路径
Transducing paths in graph classes with unbounded shrubdepth
论文作者
论文摘要
转导是表达逻辑中图（以及更普遍的关系结构）转换的一般形式主义。 We prove that a graph class $\mathscr{C}$ can be $\mathsf{FO}$-transduced from a class of bounded-height trees (that is, has bounded shrubdepth) if, and only if, from $\mathscr{C}$ one cannot $\mathsf{FO}$-transduce the class of all paths.这就建立了Blumensath和Courcelle剩下的三个公开问题之一，即$ \ Mathsf {MSO} $ - 转导准排，即使以涉及$ \ Mathsf {fo} $ - transductions而不是$ \ MATHSF {MSO} $ - 转换的更强形式。 我们证明的骨干是一个图理论语句，说明：如果图$ g $不包括路径的路径，路径的两部分补体，而半段作为半诱导的子图，则$ g $的顶点集可以分配到一个有界数的零件中，以便每个零件都构成了界限的bi bi bi bi bi bi bi bi bi of Bounded高度的高度和每个零件，并构成了每个零件，并将每个部分组成。该声明可能具有独立的利益；例如，这意味着所讨论的图形形成了一个线性$χ$结合的类。
Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class $\mathscr{C}$ can be $\mathsf{FO}$-transduced from a class of bounded-height trees (that is, has bounded shrubdepth) if, and only if, from $\mathscr{C}$ one cannot $\mathsf{FO}$-transduce the class of all paths. This establishes one of the three remaining open questions posed by Blumensath and Courcelle about the $\mathsf{MSO}$-transduction quasi-order, even in the stronger form that concerns $\mathsf{FO}$-transductions instead of $\mathsf{MSO}$-transductions. The backbone of our proof is a graph-theoretic statement that says the following: If a graph $G$ excludes a path, the bipartite complement of a path, and a half-graph as semi-induced subgraphs, then the vertex set of $G$ can be partitioned into a bounded number of parts so that every part induces a cograph of bounded height, and every pair of parts semi-induce a bi-cograph of bounded height. This statement may be of independent interest; for instance, it implies that the graphs in question form a class that is linearly $χ$-bounded.
