← All problems

Characterization conjecture for k-tight G-stable Kneser graphs

Let k≥2k\ge 2 and let GG be a graph on n≥2kn\ge 2k vertices. Define the GG-stable Kneser graph KG(G,k)KG(G,k) to have as vertices the kk-element independent sets of GG, with two vertices adjacent exactly when the corresponding independent sets are disjoint. Since χ(KG(G,k))≤n−2k+2\chi(KG(G,k))\le n-2k+2, determine precisely which graphs GG satisfy χ(KG(G,k))=n−2k+2\chi(KG(G,k))=n-2k+2. Equivalently, characterize all kk-tight graphs.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 χ(KG(G,k))≤n−2k+2\chi(KG(G,k)) \le n-2k+2 for GG-stable Kneser graphs. The new paper studies this question for k≥3k \ge 3 and does not establish the conjectured sufficiency.

Known results

  • Daneshpajouh et al. characterized the graphs that are 22-tight.
  • For k≥3k \ge 3, the proposed characterization requires a necessary condition extending the 22-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 k≥3k \ge 3 and a lower bound for GG-stable Kneser graphs when GG is a disjoint union of cycles. They also derive that certain 44-regular graphs on 3k3k vertices have an independent set of size kk.

Current status (as of October 2026): The k=2k=2 case is characterized, and a necessary condition is known for k≥3k \ge 3, but the conjectured sufficiency and hence the general characterization remain open.

Sources

Solutions 0

No solutions have been posted yet.