KIAS Workshop on Combinatorics
Coloring of the square of Kneser graphs
SPEAKER | Seog-Jin Kim
INSTITUTE | Konkuk University
DATE | May 30(Thu), 2013
TIME | 15:10
PLACE | Conference room 1503, KIAS
ABSTRACT | The Kneser graph K(n,k) is the graph whose vertices are the k-elements subsets of an n-element set, with two vertices adjacent if the sets are disjoint. The square G2 of a graph G is the graph defined on V(G) such that two vertices u and v are adjacent in G2 if the distance between u and v in G is at most 2. We denote the square of the Kneser graph K(n,k) by K2(n,k). The problem of computing ¥ö(K2(n,k)), which was originally posed by F?redi, was introduced and discussed by Kim and Nakprasit (2004). Note that that A and B are adjacent in K2(n,k) if and only if A¡ûB=? or |A¡ûB|?3k-n. Therefore, K2(n,k) is the complete graph Kt where t=nCk if n?3k-1, and K2(n,k) is a perfect matching if n=2k. But for 2k+1?n?3k-2, the exact value of ¥ö(K2(n,k)) is not known. Hence it is an interesting problem to determine the chromatic number of the square of the Kneser graph K(2k+1,k) as the first nontrivial case. We will give a brief introduction of the problem, and present recent results. This talk is based on joint work with Boram Park.