| 线图上的团染色问题 |
| |
| 引用本文： | 梁作松.线图上的团染色问题[J].运筹学学报,2016,20(3):92-98. |
| |
| 作者姓名： | 梁作松 |
| |
| 作者单位： | 1. 曲阜师范大学运筹学研究所, 山东日照 276800 |
| |
| 基金项目： | 国家自然科学基金(No. 11601262), 山东省自然科学青年基金 (No. ZR2014AQ008), 中国博士后基金(No. 2016M592156) |
| |
| 摘 要： | 设G=(V,E)为简单图, G的每个至少有两个顶点的极大完全子图称为G的一个团. 图的团染色定义为给图的点进行染色使得图中没有单一颜色的团, 也就是说每一个团具有至少2种颜色.图的一个k-团染色 是指用k 种颜色给图的点着色使得图G 的每一个团至少有2种颜色.图G的团染色数\chi_{C}(G)是指最小的数k使得图G 存在k-团染色. 首先指出了完全图的线图的团染色数与推广的Ramsey 数之间的一个联系, 其次对于最大度不超过7的线图给出了一个最优团染色的多项式时间算法.
|
| 关 键 词： | 团染色 多项式时间算法 线图 完全图 |
| 收稿时间： | 2016-01-11 |
The clique-coloring problem in line graphs |
| |
| LIANG Zuosong.The clique-coloring problem in line graphs[J].OR Transactions,2016,20(3):92-98. |
| |
| Authors: | LIANG Zuosong |
| |
| Institution: | 1. Institution of Operational Research, Qufu Normal University, Rizhao 276800, Shandong, China |
| |
| Abstract: | 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 \chi_{C}(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. |
| |
| Keywords: | clique-coloring polynomial-time algorithm line graph complete graph |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
