Stahl's multichromatic-number conjecture for Kneser graphs

About 10 years old · traced to

Let K(m,n)K(m,n) be the Kneser graph whose vertices are the nn-subsets of {1,…,m}\{1,\ldots,m\}, with two vertices adjacent when the corresponding subsets are disjoint. For an integer rr, let χr(H)\chi_r(H) be the least integer ss such that HH admits a homomorphism to K(s,r)K(s,r). Stahl's conjecture. If k=an+bk=an+b, where a≥1a\geq 1 and 0≤b≤n−10\leq b\leq n-1, then for m≥2nm\geq 2n,

χk(K(m,n))=χan(K(m,n))+χb(K(m,n))=(a+1)m−2(n−b).\chi_k(K(m,n))=\chi_{an}(K(m,n))+\chi_b(K(m,n))=(a+1)m-2(n-b).

This conjecture concerns the exact multichromatic numbers of Kneser graphs and is used in the paper to derive stronger lower bounds for chromatic numbers of exponential graphs. Its resolution is not specified in the supplied text.

References

Primary source

Claude Tardif and Xuding Zhu, “A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function”, arXiv:1906.03748 (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:1607.08780.

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.