Directed Hamiltonicity in Generalized Kneser Graphs

Abstract

We prove that the canonical orientation of the generalized Kneser graph $KG(n,k,s)$ contains a directed Hamiltonian cycle for all integers $s\ge 3$ and $n>sk$. Furthermore, we establish that the dichromatic number of this oriented graph is exactly $k$. As a special case, our results apply to the $s$-stable Kneser graphs $K_{s\text{-stab}}(n,k)$, resolving their directed Hamiltonicity and dichromatic number. Our proof adapts the class graph framework of Ledezma and Pastine to the directed setting, leveraging cyclic rotations and friend class adjacencies to construct a single directed cycle spanning all vertices. This work provides a unified and strengthened perspective on the Hamiltonian properties of Kneser-type graphs.

The current version no longer reflects the intended scope and mathematical rigor of the work