CAJ | 학술논문

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．
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.