论文标题
集团宽度：利用原子的力量
Clique-Width: Harnessing the Power of Atoms
论文作者
论文摘要
许多NP完整的图形问题是在有界集团宽度的图类别上可溶可溶可的。这些问题中的几个问题是在遗传图类$ {\ cal g} $上可溶解的多项式时间，如果它们在$ {\ cal g} $的原子（无clique cut-stet）上。因此，我们启动了一项系统的研究，研究了遗传图类别原子集团的界限。如果$ h $不是$ g $的诱发子图，则图$ g $是$ h $ - free，并且是$（h_1，h_2）$ - 如果两者都是$ h_1 $ - free和$ h_2 $ -free，则免费。当且仅当其原子具有此属性时，一类$ h $ free图具有有限的集团宽度。对于$（H_1，H_2）$ - 免费图形而不再是正确的，这是一个已知示例所证明的。我们证明了另一对$（H_1，H_2）$的存在，并对$（H_1，H_2）$ - 除18个情况以外的所有情况下的clique-width的有限性分类。
Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph class ${\cal G}$ if they are so on the atoms (graphs with no clique cut-set) of ${\cal G}$. Hence, we initiate a systematic study into boundedness of clique-width of atoms of hereditary graph classes. A graph $G$ is $H$-free if $H$ is not an induced subgraph of $G$, and it is $(H_1,H_2)$-free if it is both $H_1$-free and $H_2$-free. A class of $H$-free graphs has bounded clique-width if and only if its atoms have this property. This is no longer true for $(H_1,H_2)$-free graphs, as evidenced by one known example. We prove the existence of another such pair $(H_1,H_2)$ and classify the boundedness of clique-width on $(H_1,H_2)$-free atoms for all but 18 cases.
