Meunier's chromatic number conjecture for stable Kneser graphs

About 10 years old · traced to

Let KG(n,k)s−stabKG(n,k)_{s-\mathrm{stab}} be the induced subgraph of the Kneser graph KG(n,k)KG(n,k) on the ss-stable kk-subsets of [n][n], where a subset AA is ss-stable when s≤∣i−j∣≤n−ss\leq |i-j|\leq n-s for every pair of distinct elements i,j∈Ai,j\in A. Meunier's conjecture. If n,k,sn,k,s are non-negative integers such that n≥skn\geq sk and s≥2s\geq 2, then

χ(KG(n,k)s−stab)=n−s(k−1).\chi\left(KG(n,k)_{s-\mathrm{stab}}\right)=n-s(k-1).

This generalizes the chromatic-number formula for Schrijver graphs, which are the case s=2s=2. The source presents the assertion as Meunier's conjecture; no resolution is given in the supplied text.

References

Primary source

Hamid Reza Daneshpajouh and József Osztényi, “On the neighborhood complex of s-stable Kneser graphs”, arXiv:1904.08219 (2019).

Additional references

2 papers in this index state this conjecture (2016–2019). The statement above is taken from the most recent of them; the others are arXiv:1604.07023.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.