Computational sciences Conferences 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
Keyword  |
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.
• On Combinatorial pro...
Younjin Kim
June 1(Sat), 2013
• Flag enumeration of ...
Sangwook Kim
June 1(Sat), 2013
• Classi?cation of reg...
Youngsoo Kwon
May 31(Fri), 2013
Mitsugu Hirasaka
May 31(Fri), 2013
• Fractional weak disc...
Jeong Ok Choi
May 31(Fri), 2013
• Balanced labellings ...
Hwanchul Yoo
May 31(Fri), 2013
• Colored permutations...
Seunghyun Seo
May 31(Fri), 2013
• The Riordan group an...
Gi-Sang Cheon
May 30(Thu), 2013
• Polytope numbers and...
Hyun Kwang Kim
May 30(Thu), 2013
• Coloring of the squa...
Seog-Jin Kim
May 30(Thu), 2013