media archive
Computational sciences Conferences KIAS Workshop on Combinatorics
Loading the player ...
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  |  
Download  |  
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 AB=? or |AB|?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
  • Zeta functions of ad...
    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