论文标题
$ 2 $ - 极性和算法的极性变体上的cograph超类别
$2$-polarity and algorithmic aspects of polarity variants on cograph superclasses
论文作者
论文摘要
图形$ g $据说是$（s，k）$ - 极性图，如果其顶点套件承认分区$（a，b）$，这样$ a $ a $ b $ a $ a $ b $ tocuce a $ a $ b $ tocuce a $ a $ b $均可诱导完整的$ s $ partite图形和最多$ k $ k $ k $完整图的分离。极性图和单极图分别定义为$（\ infty，\ infty）$ - 和$（1，\ infty）$ - 极性图，而单极图是具有极地分区$（a，b）$的图形，因此$ a $ a $是一个集团。 已知决定任意图是极图还是单极图是NP完整的问题。相反，决定图是否是单极图，可以在多项式时间内完成。在这项工作中，我们证明可以在$ p_4 $ -sparse和$ p_4 $ - 延伸图的类别上以线性时间解决三个问题，从而概括了先前以Cobshss闻名的类似结果。 此外，我们为$（2,2）$ - Polar Graphs $ p_4 $ -sparse和$ p_4 $ - 扩展图提供有限的禁止子图特征，还概括了最近获得的Cobhaphs类的类似结果。
A graph $G$ is said to be an $(s, k)$-polar graph if its vertex set admits a partition $(A, B)$ such that $A$ and $B$ induce, respectively, a complete $s$-partite graph and the disjoint union of at most $k$ complete graphs. Polar graphs and monopolar graphs are defined as $(\infty, \infty)$- and $(1, \infty)$-polar graphs, respectively, and unipolar graphs are those graphs with a polar partition $(A, B)$ such that $A$ is a clique. The problems of deciding whether an arbitrary graph is a polar graph or a monopolar graph are known to be NP-complete. In contrast, deciding whether a graph is a unipolar graph can be done in polynomial time. In this work we prove that the three previous problems can be solved in linear time on the classes of $P_4$-sparse and $P_4$-extendible graphs, generalizing analogous results previously known for cographs. Additionally, we provide finite forbidden subgraph characterizations for $(2,2)$-polar graphs on $P_4$-sparse and $P_4$-extendible graphs, also generalizing analogous results recently obtained for the class of cographs.
