Improved bounds on the chromatic numbers of the square of Kneser graphs

preprint2013arXivOpen access

Abstract

The Kneser graph K(n,k)K(n,k) is the graph whose vertices are the kk-elements subsets of an nn-element set, with two vertices adjacent if the sets are disjoint. The square G2G^2 of a graph GG is the graph defined on V(G)V(G) such that two vertices uu and vv are adjacent in G2G^2 if the distance between uu and vv in GG is at most 2. Determining the chromatic number of the square of the Kneser graph K(2k+1,k)K(2k+1, k) is an interesting problem, but not much progress has been made. Kim and Nakprasit \cite{2004KN} showed that χ(K2(2k+1,k))≤4k+2χ(K^2(2k+1,k)) \leq 4k+2, and Chen, Lih, and Wu \cite{2009CLW} showed that χ(K2(2k+1,k))≤3k+2χ(K^2(2k+1,k)) \leq 3k+2 for k≥3k \geq 3. In this paper, we give improved upper bounds on χ(K2(2k+1,k))χ(K^2(2k+1,k)). We show that χ(K2(2k+1,k))≤2k+2χ(K^2(2k+1,k)) \leq 2k+2, if 2k+1=2n−1 2k +1 = 2^n -1 for some positive integer nn. Also we show that χ(K2(2k+1,k))≤83k+203χ(K^2(2k+1,k)) \leq \frac{8}{3}k+\frac{20}{3} for every integer k≥2k\ge 2. In addition to giving improved upper bounds, our proof is concise and can be easily understood by readers while the proof in \cite{2009CLW} is very complicated. Moreover, we show that χ(K2(2k+r,k))=Θ(kr)χ(K^2(2k+r,k))=Θ(k^r) for each integer 2≤r≤k−22 \leq r \leq k-2.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.