完美图

扩展释义

完美图(perfect graph)是一种特殊的简单图，若图G的任意一个节点导出图H的色数χ(H)等于H的团数，则称G是χ完美图。若图G的任意一个节点导出子图H的独立数α(H)等于H的团划分数，则称G是α完美图，弱完美图猜想：G是χ完美图的充分必要条件是G为α完美图；或等价地，完美图的补图是完美图。由于它已获证，并称为完美图定理，这就允许不必区别χ完美图和α完美图，而统称为完美图，强完美图猜想：G是完美图当且仅当G和G的补图GC都不含长大于3的奇圈作为节点导出子图，这个猜想至今尚未得到证明。