Stahl's multichromatic-number conjecture for Kneser graphs

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 a1a\geq 1 and 0bn10\leq b\leq n-1, then for m2nm\geq 2n,

χk(K(m,n))=χan(K(m,n))+χb(K(m,n))=(a+1)m2(nb).\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.

Sources & referencesView supporting material

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.