Kneser图KG（11，5）平方图的色数

摘要

Kneser图KG（n，k）的顶点集包括一个n元集的所有k元子集，其中的任意两个顶点相邻当且仅当它们对应的子集不相交．一个图G的平方图G 2的顶点集与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.