Triangle-free Hamiltonian Kneser graphs

The Kneser graph K(n,k) has as vertices the k-subsets of {1,2, …, n}. Two vertices are adjacent if the k-sets are disjoint. When n<3k, the Kneser Graph K(n,k) has no triangle. In this paper, we prove that K(n,k) is Hamiltonian for n⩾(3k+1+5k2−2k+1)/2, and extend this to the bipartite Kneser graphs. Note that (3k+1+5k2−2k+1)/2<2.62k+1.