主题
Search

弱完美图


弱完美图是指满足 omega(G)=chi(G) 的图(不要求此条件在导出子图上仍然成立,完美图则需要满足此条件,完美图), 其中 omega(G)团数chi(G)色数

所有完美图都是弱完美图。

节点数为 n=1, 2, ... 的弱完美图的数量分别为 1, 2, 4, 11, 33, 152, 1006, 11805, ... (OEIS A198634)。


参见

色数, 团数, 完美图, 强完美图

使用 Wolfram|Alpha 探索

参考文献

Maimani, H. R.; Pournaki, M. ä.; and Yassemi, S. "A Class of Weakly Perfect Graphs." Czech. Math. J. 60, 1037-1041, 2010.Sloane, N. J. A. 序列 A198634,出自“整数序列在线百科全书”。

引用为

Eric W. Weisstein. “弱完美图。” 来自 MathWorld-- Wolfram Web 资源。 https://mathworld.net.cn/WeaklyPerfectGraph.html

主题分类