| 引用本文： |
-
许晓东,梁美莲,邵泽辉.Kneser图KG(11,5)平方图的色数[J].广西科学,2014,21(3):287-289. [点击复制]
- XU Xiao-dong,LIANG Mei-lian,SHAO Ze-hui.The Chromatic Number of the Square of Kneser Graph KG(11,5)[J].Guangxi Sciences,2014,21(3):287-289. [点击复制]
|
|
| 摘要: |
| Kneser图KG(n,k)的顶点集包括一个n元集的所有k元子集,其中的任意两个顶点相邻当且仅当它们对应的子集不相交.一个图G的平方图G2的顶点集与G的顶点集相同,在G2中两个顶点之间有边当且仅当它们在G中的距离不超过2.通过理论分析和计算机搜索,得到8 ≤ χ(KG2(11,5))≤ 10,10 ≤ χ(KG2(13,6))≤ 16,其中前一个结论改进了已知的下界7和上界12. |
| 关键词: 色数 Kneser图 平方图 |
| DOI：10.13656/j.cnki.gxkx.20140616.003 |
| 投稿时间：2013-04-07修订日期：2013-09-10 |
| 基金项目:国家自然科学基金项目(11361008)资助。 |
|
| The Chromatic Number of the Square of Kneser Graph KG(11,5) |
|
XU Xiao-dong1, LIANG Mei-lian2, SHAO Ze-hui3,4
|
| (1.Guangxi Academy of Sciences, Nanning, Guangxi, 530007, China;2.School of Mathematics and Information Science, Guangxi University, Nanning, Guangxi, 530004, China;3.Key Laboratory of Pattern Recognition and Intelligent Information Processing, Institutions of Higher Education of Sichuan Province, Chengdu, Sichuan, 610106, China;4.School of Information Science and Technology, Chengdu University, Chengdu, Sichuan, 610106, China) |
| Abstract: |
| The Kneser graph KG (n, k) is the graph whose vertex set consists of all k-subsets of an n-set, and two vertices are adjacent if and only if they are disjoint.The square G2 of a graph G is defined on the vertex set of G such that distinct vertices within distancetwo in G are joined by an edge.By theoretical analysis and computer search, we obtain that 8 ≤ χ (KG2 (11, 5)) ≤ 10, which improves the known lower bound 7 and upper bound 12, and that 10 ≤ χ (KG2 (13, 6)) ≤ 16. |
| Key words: chromatic number Kneser graph square graph |
