| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

8. Chromatic number of generalized Kneser graphs

    1. Chromatic number of generalized Kneser graphs

          We define generalized Kneser graph $KG_s(n,k)$ by its vertex set containing every size-$k$ subset $K \subset [n]$ with $s\leq |i-j|\leq n-s$ ($\forall i,j\in K$), and its edge set containing every disjoint pair.

      Add remark

      Problem 8.1.

      [Shira Zerbib] Is it true that for $n > sk$, the chromatic number $\chi(KG_s(n,k)) = n - sk +s$?
          Note: 1. Lovasz proved $\chi(KG_1(n,k)) = n - 2k +2$ for $n > 2k$. 2. Schrijver proved $\chi(KG_2(n,k)) = n - 2k +2$ for $n > 2k$. 3. Jonsson proved this statement for $s \geq 4$ and $n$ large. Chen proved this conjecture for $s$ being even.

      Reference: L. Lovasz. Kneser’s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series B 25 (1978): 319–324.

      A. Schrijver. Vertex-critical subgraphs of Kneser graphs. Nieuw Archief voor Wiskunde 26(3) (1978): 454–461.

      J. Jonsson. On the chromatic number of generalized stable Kneser graphs. Unpublished preprint, available at https://people.kth.se/jakobj/research.html (2012).

      P.-A. Chen. On the multichromatic number of s‐stable Kneser graphs. Journal of Graph Theory 79(3) (2015): 233–248.

          Cite this as: AimPL: Albertson conjecture and related problems, available at http://aimpl.org/albertson.