Maximum cocliques in the projective-plane Johnson graph

Let q>2q>2 and consider the graph Γq(q2+q+1,q+1)\Gamma_q(q^2+q+1,q+1) on the (q+1)(q+1)-subsets of a (q2+q+1)(q^2+q+1)-set, with adjacency determined by the Johnson-scheme relation indexed by qq. A maximum coclique is a coclique of largest possible cardinality.

Projective-plane coclique conjecture. For q>2q>2, a coclique of maximum size in the graph Γq(q2+q+1,q+1)\Gamma_q(q^2+q+1,q+1) must consist of all the (q+1)(q+1)-sets containing two given points; so the chromatic number of this graph is strictly larger than q2+q+1q^2+q+1.

The paper reports that the conjecture holds for q=3q=3 and q=4q=4. It concerns the relationship between projective planes, extremal cocliques, and synchronization versus separation in Johnson schemes.

Sources & referencesView supporting material

Primary source

Mohammed Aljohani, John Bamberg and Peter J. Cameron, “Synchronization and separation in the Johnson schemes”, arXiv:1706.01365 (2017).

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.