English

运筹学学报

• 运筹学 • 上一篇    下一篇

线图上的团染色问题

梁作松1,*   

  1. 1. 曲阜师范大学运筹学研究所, 山东日照 276800
  • 收稿日期:2016-01-11 出版日期:2016-09-15 发布日期:2016-09-15
  • 通讯作者: 梁作松 liangzuosong@126.com
  • 基金资助:

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

The clique-coloring  problem in line graphs

LIANG Zuosong1,*   

  1. 1. Institution of Operational Research,  Qufu Normal University, Rizhao 276800, Shandong, China
  • Received:2016-01-11 Online:2016-09-15 Published:2016-09-15

PDF

357

摘要：

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

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

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.

Key words: clique-coloring, polynomial-time algorithm, line graph, complete graph