Johnson–Holroyd–Stahl conjecture on the circular chromatic number of Kneser graphs

Let KG(m,n){\rm KG}(m,n) denote the Kneser graph, whose vertices are the nn-element subsets of an mm-element set, with two vertices adjacent when the corresponding subsets are disjoint. Write χ(G)\chi(G) for the chromatic number and χc(G)\chi_c(G) for the circular chromatic number. Johnson–Holroyd–Stahl conjecture. For all m2n+1m\geq 2n+1,

χc(KG(m,n))=χ(KG(m,n)).\chi_c({\rm KG}(m,n))=\chi({\rm KG}(m,n)).

Equality of the two chromatic parameters is known in several cases, including m2n+2m\leq 2n+2 or n=2n=2, but the statement was presented as a conjecture for all Kneser graphs in the source.

Sources & referencesView supporting material

Primary source

Hossein Hajiabolhassan and Ali Taherkhani, “Graph Powers and Graph Homomorphisms”, arXiv:0808.0362 (2008).

Additional references

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

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.