Characterization conjecture for k-tight G-stable Kneser graphs
Let and let be a graph on vertices. Define the -stable Kneser graph to have as vertices the -element independent sets of , with two vertices adjacent exactly when the corresponding independent sets are disjoint. Since , determine precisely which graphs satisfy . Equivalently, characterize all -tight graphs.
References
- The chromatic number of G-stable Kneser graphs — arXiv — Carmen Arana, Penny Haxell, Tomáš Kaiser, Matěj Stehlík
Source: arXiv
Progress summary
A new unrefereed paper proves only a necessary condition for the proposed characterization, so the general conjecture remains open.
The conjecture asks which graphs attain the upper bound for -stable Kneser graphs. The new paper studies this question for and does not establish the conjectured sufficiency.
Known results
- Daneshpajouh et al. characterized the graphs that are -tight.
- For , the proposed characterization requires a necessary condition extending the -tight case, but its sufficiency is only conjectured.
October 2026 necessary-condition result
Carmen Arana, Penny Haxell, Tomáš Kaiser, and Matěj Stehlík prove the stated necessary condition for and a lower bound for -stable Kneser graphs when is a disjoint union of cycles. They also derive that certain -regular graphs on vertices have an independent set of size .
Current status (as of October 2026): The case is characterized, and a necessary condition is known for , but the conjectured sufficiency and hence the general characterization remain open.
Sources
Solutions 0
No solutions have been posted yet.