Coloring of the square of Kneser graph K(2k+r,k)K(2k+r,k)

preprint2014arXivOpen access

Abstract

The Kneser graph K(n,k)K(n,k) is the graph whose vertices are the kk-element subsets of an nn elements set, with two vertices adjacent if they 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(n,k)K(n, k) is an interesting graph coloring problem, and is also related with intersecting family problem. The square of K(2k,k)K(2k, k) is a perfect matching and the square of K(n,k)K(n, k) is the complete graph when n≥3k−1n \geq 3k-1. Hence coloring of the square of K(2k+1,k)K(2k +1, k) has been studied as the first nontrivial case. In this paper, we focus on the question of determining χ(K2(2k+r,k))χ(K^2(2k+r,k)) for r≥2r \geq 2. Recently, Kim and Park \cite{KP2014} showed that χ(K2(2k+1,k))≤2k+2χ(K^2(2k+1,k)) \leq 2k+2 if 2k+1=2t−1 2k +1 = 2^t -1 for some positive integer tt. In this paper, we generalize the result by showing that for any integer rr with 1≤r≤k−21 \leq r \leq k -2, (a) χ(K2(2k+r,k))≤(2k+r)rχ(K^2 (2k+r, k)) \leq (2k+r)^r, if 2k+r=2t2k + r = 2^t for some integer tt, and (b) χ(K2(2k+r,k))≤(2k+r+1)rχ(K^2 (2k+r, k)) \leq (2k+r+1)^r, if 2k+r=2t−12k + r = 2^t-1 for some integer tt. On the other hand, it was showed in \cite{KP2014} that χ(K2(2k+r,k))≤(r+2)(3k+3r+32)rχ(K^2 (2k+r, k)) \leq (r+2)(3k + \frac{3r+3}{2})^r for 2≤r≤k−22 \leq r \leq k-2. We improve these bounds by showing that for any integer rr with 2≤r≤k−22 \leq r \leq k -2, we have χ(K2(2k+r,k))≤2(94k+9(r+3)8)rχ(K^2 (2k+r, k)) \leq2 \left(\frac{9}{4}k + \frac{9(r+3)}{8} \right)^r. Our approach is also related with injective coloring and coloring of Johnson graph.

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.