此条目可参照英语维基百科相应条目来扩充.
若您熟悉来源语言和主题,请协助参考外语维基百科扩充条目.请勿直接提交机械翻译,也不要翻译不可靠,低品质内容.依版权协议,译文需在编辑摘要注明来源,或于讨论页顶部标记{{Translated page}}标签.
团(英语:clique)是一个图中两两相邻的顶点构成的集合.最大团是一个图中顶点最多的团,它的定点数被称为 G {\displaystyle G}
满足如下关系:
色数和独立数(independence number)
独立集(英语:independent set)是一个图中两两不相邻的顶点所构成的集合.最大独立集是一个图中顶点最多的独立集,它的定点数被称为 G {\displaystyle G}
色多项式(英语:chromatic polynomial)是将一个图G进行t-着色的方法数,记作P(G t).P(G t)是关于t的多项式,假设G的阶数为n,则P(G t)满足如下性质:
首项系数为1;
色多项式包含了G是否能进行t-着色的信息,即可以根据色多项式确定G的色数.二者具有如下关系: