English

运筹学学报 ›› 2013, Vol. 17 ›› Issue (4): 103-108.

• 运筹学 • 上一篇    下一篇

几类积图的团染色数

单而芳1,*, 叶婷婷2   

  1. 1. 上海大学管理学院, 上海 200444；  2. 上海大学数学系, 上海 200444；
  • 出版日期:2013-12-15 发布日期:2013-12-15
  • 通讯作者: 单而芳 E-mail:efshan@shu.edu.cn
  • 基金资助:

    基金项目：国家自然科学基金 (No. 11171207)

Clique-coloring numbers of some product graphs

SHAN Erfang1,*, YE Tingting2   

  1. 1. School of Management, Shanghai University, Shanghai 200444, China; 2. Department of Mathematics, Shanghai University, Shanghai 200444, China
  • Online:2013-12-15 Published:2013-12-15

PDF

932

摘要： 设G=(V, E)为简单图, V和E分别表示图的点集和边集. 图G的一个k-团染色是指点集V到色集{1, 2,...,k}的一个映射, 使得G的每个至少含两个点的极大团都至少有两种颜色. 分别给出了任意两个图的团色数与它们通过笛卡尔积、Kronecker积、强直积或字典积运算后得到的积图的团色数之间的关系.

关键词: 团染色, 笛卡尔积, Kronecker积, 强直积, 字典积

Abstract: Let G=(V, E) be a simple graph with vertex set V and edge set E. A k-clique-coloring of G is a mapping $\phi: V\rightarrow {1, 2, ...,  k},  such that no maximal clique of size at least two is monochromatic. The clique-coloring number of G is the smallest k for which c is a k-clique-coloring of G.  In this paper we investigate the clique-coloring numbers of Cartesian product, Kronecker product, strong product and lexicographical product of two graphs.

Key words: clique coloring, Cartesian product, Kronecker product, strong product, lexicographical product

中图分类号: