Kneser图KG(11,5)平方图的色数(英文)  

The Chromatic Number of the Square of Kneser Graph KG(11,5)

作　　者：许晓东[1] 梁美莲[2] 邵泽辉[3,4] 

机构地区：[1]广西科学院,广西南宁530007 [2]广西大学数学与信息科学学院,广西南宁530004 [3]四川省高校模式识别与智能信息处理重点实验室,四川成都610106 [4]成都大学信息科学与技术学院,四川成都610106

出　　处：《广西科学》2014年第3期287-289,共3页Guangxi Sciences

基　　金：国家自然科学基金项目(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.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.

关 键 词：色数 Kneser图 平方图 

分 类 号：O175[理学—数学]