设G=(V,E)为简单图,G的每个至少有两个顶点的极大完全子图称为G的一个团.图的团染色定义为给图的点进行染色使得图中没有单一颜色的团,也就是说每一个团具有至少2种颜色.图的一个k-团染色是指用k种颜色给图的点着色使得图G的每一个团至少有2种颜色.图G的团染色数χC(G)是指最小的数k使得图G存在k-团染色.首先指出了完全图的线图的团染色数与推广的Ramsey数之间的一个联系,其次对于最大度不超过7的线图给出了一个最优团染色的多项式时间算法.
科研之友
微信
新浪微博
Facebook
分享链接
