主题
Search

禁用次子图

如果一个图作为一个给定图的次子图出现，并导致该图不属于某个图族，则该图被称为禁用次子图。

更一般地，可能存在一个次子图族，它们的出现可以表征一个给定的图是否具有某种性质。例如，平面图是一个不包含完全图 K_5 或效用图 K_(3,3) 作为次子图的图。下表总结了一些具有禁用次子图障碍的简单图族。

图族障碍
顶点图未知的有限数量的次子图；至少已知 157 个
森林C_3
无连结可嵌入图7 个 Petersen 图族 禁用次子图
外平面图K_4 和 K_(2,3)
路径宽度 <=1C_3 和 (3,2)-辐条图
路径宽度 <=2110 个禁用次子图
平面图K_5 和 K_(3,3)
射影平面图35 个禁用次子图
环面图未知的有限数量的次子图；已知数千个
树宽度 <=2K_4
树宽度 <=3K_5, 八面体图 K_(2,2,2), 棱柱图 P_2 平方 C_5, 瓦格纳图 M_4
树宽度 <=4未知的有限数量的次子图；至少已知 75 个

另请参阅

禁用导出子图, 禁用子图, 禁用拓扑次子图, Kuratowski 归约定理, 无连结可嵌入图, 外平面图, 射影平面图, 平面图, Robertson-Seymour 定理, Wagner 定理

使用 Wolfram|Alpha 探索

参考文献

Peirce, M. "Minor-Minimal Graph Functions." https://github.com/mikepierce/MMGraphFunctions.

请按如下方式引用

Weisstein, Eric W. "禁用次子图。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/ForbiddenMinor.html

主题分类