论文标题
树宽度二分法
Tree-width dichotomy
论文作者
论文摘要
我们证明，当有限集$ f $ f $ f $ f $ f $时，只有$ f $包含完整的图形，完整的两部分图，三脚架，三脚架（每个连接的森林中，每个连接的组件最多有3片）和三脚架的线图时，我们才有有限的f $ f $ f $ f $ f $ f $ f $ f $ f $ f $ f $ f $ f限制，我们证明了由有限的禁止诱导子图的有限套装的遗传类别的图形。
We prove that the tree-width of graphs in a hereditary class defined by a finite set $F$ of forbidden induced subgraphs is bounded if and only if $F$ includes a complete graph, a complete bipartite graph, a tripod (a forest in which every connected component has at most 3 leaves) and the line graph of a tripod.
