Maximum cocliques in the projective-plane Johnson graph
Let and consider the graph on the -subsets of a -set, with adjacency determined by the Johnson-scheme relation indexed by . A maximum coclique is a coclique of largest possible cardinality.
Projective-plane coclique conjecture. For , a coclique of maximum size in the graph must consist of all the -sets containing two given points; so the chromatic number of this graph is strictly larger than .
The paper reports that the conjecture holds for and . 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
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.