Maximum cocliques in the projective-plane Johnson graph

About 9 years old · traced to

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.

References

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.