Short proof that Kneser graphs are Hamiltonian for n≥ 4k

2019/12/17 by Johann Bellmann, Bellmann, Johann, Bjarne Schülke +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1912.08186

3 pages

arxiv created 2019/12/17 · arxiv updated 2019/12/18

Abstract

For integers n≥ k≥ 1, the Kneser graph K(n,k) is the graph with vertex set V=[n]^(k) and edge set E=\\x,y\ ∈ V⁽²⁾: x∩ y=∅\. Chen proved that for n≥ 3k, Kneser graphs are Hamiltonian and later improved this to n≥ 2.62k+1. Furthermore, Chen and Füredi gave a short proof that if k | n, Kneser graphs are Hamiltonian for n≥ 3k. In this note, we present a short proof that does not need the divisibility condition, i.e., we give a short proof that K(n,k) is Hamiltonian for n≥ 4k.

Related

• Clique factors in Kneser graphs
• Kneser graphs are Hamiltonian
• Sparse Kneser graphs are Hamiltonian
• s-Stable Kneser Graph are Hamiltonian
• Directed Hamiltonicity in Generalized Kneser Graphs