{
  "id": "1305.2567",
  "version": "v1",
  "published": "2013-05-12T07:43:32.000Z",
  "updated": "2013-05-12T07:43:32.000Z",
  "title": "Improved bounds on the chromatic numbers of the square of Kneser graphs",
  "authors": [
    "Seog-Jin Kim",
    "Boram Park"
  ],
  "categories": [
    "math.CO"
  ],
  "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 $G^2$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^2$ if the distance between $u$ and $v$ in $G$ is at most 2. Determining the chromatic number of the square of the Kneser graph $K(2k+1, k)$ is an interesting problem, but not much progress has been made. Kim and Nakprasit \\cite{2004KN} showed that $\\chi(K^2(2k+1,k)) \\leq 4k+2$, and Chen, Lih, and Wu \\cite{2009CLW} showed that $\\chi(K^2(2k+1,k)) \\leq 3k+2$ for $k \\geq 3$. In this paper, we give improved upper bounds on $\\chi(K^2(2k+1,k))$. We show that $\\chi(K^2(2k+1,k)) \\leq 2k+2$, if $ 2k +1 = 2^n -1$ for some positive integer $n$. Also we show that $\\chi(K^2(2k+1,k)) \\leq \\frac{8}{3}k+\\frac{20}{3}$ for every integer $k\\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 $\\chi(K^2(2k+r,k))=\\Theta(k^r)$ for each integer $2 \\leq r \\leq k-2$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-05-12T07:43:32.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "kneser graph",
      "chromatic number",
      "upper bounds",
      "elements subsets",
      "element set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1305.2567K"
    }
  }
}