论文标题
解析素数模块：伪描绘的结构和可解释的图形
Resolving Prime Modules: The Structure of Pseudo-cographs and Galled-Tree Explainable Graphs
论文作者
论文摘要
图形$ g $的模块化分解是一种自然结构，可在标记的树$（t，t）$方面捕获$ g $的关键特征，其顶点被标记为“系列”（$ 1 $），“并行”（$ 0 $）或“ prime”。但是，$ g $的全部信息仅由其模块化分解树$（t，t）$提供，如果$ g $是cograph，即$ g $不包含Prime模块。在这种情况下，$（t，t）$解释$ g $，即$ \ {x，x，y \} \ in E（g）$ in E（g）$，并且仅是当时最低的共同祖先$ \ mathrm {lca} _t（x，x，x，y）$ x $的$ x $和$ y $ y $ $ $ $ $ $ $ y label” $ 1 $”。伪描绘，或更通用的Gatex Graphs $ g $是可以通过标记的壁炉树（即标记为网络$（N，T）$来解释的图形，这些图是从模块化分解树$（t，t）$ G $中获得的$ G $的$ g $的$（t）$，通过简单的cycles cycles cycles cycles更换$ g $。可以在线性时间内构建这些图形的Gatex图可以识别并标记为累积的树。 在此贡献中，我们根据集合$ \ mathfrak {f} _ {\ mathrm {gt}} $ 25禁止诱导子图表的$。反过来，这种表征使我们能够证明Gatex图与许多其他知名的图形类别密切相关，例如$ P_4 $ -SPARSE和$ P_4 $ - 可更高的图形，虚弱的图形，具有完美的顺序，可比较性和置换图的完美图形，模糊的图形，模糊的图形，Meyniel图形，间隔图，非常强的图形或非常强的图形和非常强的图形和brirttly-perfects和britterflect。此外，我们表明，每个Gatex图最多在1处为双宽度，并提供线性时间算法，以通过利用基础盖的结构来解决Gatex图上的几个NP硬问题（Clique，Clique，Coloring，独立集），他们解释了。
The modular decomposition of a graph $G$ is a natural construction to capture key features of $G$ in terms of a labeled tree $(T,t)$ whose vertices are labeled as "series" ($1$), "parallel" ($0$) or "prime". However, full information of $G$ is provided by its modular decomposition tree $(T,t)$ only, if $G$ is a cograph, i.e., $G$ does not contain prime modules. In this case, $(T,t)$ explains $G$, i.e., $\{x,y\}\in E(G)$ if and only if the lowest common ancestor $\mathrm{lca}_T(x,y)$ of $x$ and $y$ has label "$1$". Pseudo-cographs, or, more general, GaTEx graphs $G$ are graphs that can be explained by labeled galled-trees, i.e., labeled networks $(N,t)$ that are obtained from the modular decomposition tree $(T,t)$ of $G$ by replacing the prime vertices in $T$ by simple labeled cycles. GaTEx graphs can be recognized and labeled galled-trees that explain these graphs can be constructed in linear time. In this contribution, we provide a novel characterization of GaTEx graphs in terms of a set $\mathfrak{F}_{\mathrm{GT}}$ of 25 forbidden induced subgraphs. This characterization, in turn, allows us to show that GaTEx graphs are closely related to many other well-known graph classes such as $P_4$-sparse and $P_4$-reducible graphs, weakly-chordal graphs, perfect graphs with perfect order, comparability and permutation graphs, murky graphs as well as interval graphs, Meyniel graphs or very strongly-perfect and brittle graphs. Moreover, we show that every GaTEx graph as twin-width at most 1 and and provide linear-time algorithms to solve several NP-hard problems (clique, coloring, independent set) on GaTEx graphs by utilizing the structure of the underlying galled-trees they explain.
