主题
Search

图洞


Chvátal 将术语“洞”定义为“长度至少为四的无弦圈”。“长度至少为四”的限制允许使用术语“洞”,而无需考虑“无弦圈”的定义是否已经排除长度为 3 的圈(例如,West 2002, p. 225)或将其包括在内(Cook 2012, p. 197; Wikipedia)。

如果图洞具有偶数个顶点,则称为偶洞;如果具有奇数个顶点,则称为奇洞。图洞的图补称为图反洞。没有奇洞是完美图(因为奇洞的团数为 2,其色数为 3)。


另请参阅

Berge 图, 无弦圈, 图反洞, 图圈, 强完美图定理

使用 Wolfram|Alpha 探索

参考文献

Chvátal, V. "强完美图定理。" http://www.cs.concordia.ca/~chvatal/perfect/spgt.htmlCook, K.; Eschen, E. M.; Sritharan, R.; 和 Wang, X. "完成着色图以满足目标属性。" 收录于 计算机科学中的图论概念:第 39 届国际研讨会,WG 2013,德国吕贝克,2013 年 6 月 19-21 日,修订论文集。 Ed. A. Brandstädt, K. Jansen, 和 R. Reischuk)。德国柏林:â-¢Springer,pp. 189-200, 2013。West, D. B. 图论导论,第 2 版。 Englewood Cliffs, NJ: Prentice-Hall, p. 225, 2000。Wikipedia 贡献者。 "导出路径。" 维基百科,自由的百科全书。维基百科,自由的百科全书。 2020 年 8 月 7 日;检索于 2020 年 9 月 4 日。 https://en.wikipedia.org/wiki/Induced_path

在 Wolfram|Alpha 中被引用

图洞

请引用为

Weisstein, Eric W. "图洞。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/GraphHole.html

主题分类