线图上的团染色问题  

The clique-coloring problem in line graphs

作　　者：梁作松[1] 

机构地区：[1]曲阜师范大学运筹学研究所,山东日照276800

出　　处：《运筹学学报》2016年第3期92-98,共7页Operations Research Transactions

基　　金：国家自然科学基金(No.11601262);山东省自然科学青年基金(No.ZR2014AQ008);中国博士后基金(No.2016M592156)

摘　　要：设G=(V,E)为简单图,G的每个至少有两个顶点的极大完全子图称为G的一个团.图的团染色定义为给图的点进行染色使得图中没有单一颜色的团,也就是说每一个团具有至少2种颜色.图的一个k-团染色是指用k种颜色给图的点着色使得图G的每一个团至少有2种颜色.图G的团染色数χC(G)是指最小的数k使得图G存在k-团染色.首先指出了完全图的线图的团染色数与推广的Ramsey数之间的一个联系,其次对于最大度不超过7的线图给出了一个最优团染色的多项式时间算法.A clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that no clique of G is monochromatic. If G has a k- clique-coloring, we say that G is k-clique-colorable. The clique-coloring number xc（G） is the smallest integer k admitting a k-clique-coloring of G. In this paper, we first point out a relation between the clique-coloring number of line graphs of complete graphs and the generalized Ramsey number. Secondly, we give a polynomial time algorithm for the optimal clique-coloring problem in line graphs of maximum degree at most 7.

关 键 词：团染色 多项式时间算法 线图 完全图 

分 类 号：O157.5[理学—数学]