| Kneser图KG(11,5)平方图的色数 |
| |
| 引用本文： | 许晓东,梁美莲,邵泽辉.Kneser图KG(11,5)平方图的色数[J].广西科学,2014,21(3):287-289. |
| |
| 作者姓名： | 许晓东 梁美莲 邵泽辉 |
| |
| 作者单位： | [1]广西科学院,广西南宁530007; [2]广西大学数学与信息科学学院,广西南宁530004; [3]四川省高校模式识别与智能信息处理重点实验室,四川成都610106; [4]成都大学信息科学与技术学院,四川成都610106 |
| |
| 基金项目： | 国家自然科学基金项目（11361008）资助. |
| |
| 摘 要： | 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图 平方图 |
| 收稿时间： | 2013/4/7 0:00:00 |
| 修稿时间： | 2013/9/10 0:00:00 |
The Chromatic Number of the Square of Kneser Graph KG(11,5) |
| |
| XU Xiao-dong,LIANG Mei-lian and SHAO Ze-hui.The Chromatic Number of the Square of Kneser Graph KG(11,5)[J].Guangxi Sciences,2014,21(3):287-289. |
| |
| Authors: | XU Xiao-dong LIANG Mei-lian and SHAO Ze-hui |
| |
| Institution: | XU Xiao-dong, LIANG Mei-lian, SHAO Ze-hui(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 adj acent if and only if they are disj oint.The square G2 of a graph G is defined on the vertex set of G such that distinct vertices within distancetwo in G are j oined 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. |
| |
| Keywords: | chromatic number Kneser graph square graph |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《广西科学》浏览原始摘要信息 |
| 点击此处可从《广西科学》下载免费的PDF全文 |
|
