Cores of Cayley graphs

Status partial high confidence

The original conjecture (and even the special case $M=\mathbb{Z}_2$, the cubelike core question of Nešetřil and Šámal) remains open in general, but substantial partial results have appeared since 2007. Mančinska, Pivotto, Roberson and Royle (2020) showed that cores of cubelike graphs inherit strong structural, spectral and group-theoretic properties and verified the conjecture for cubelike graphs whose core has at most 32 vertices, while Rao and Tan (2025) proved that Cayley graphs on elementary abelian $p$-groups (any prime $p$) of degree less than $5$ or at least $5$ less than the order have complete (hence cubelike) cores, settling the extreme-degree case.

Cited literature (2)

• partial Cores of cubelike graphs (2020)
  Laura Mančinska, Irene Pivotto, David E. Roberson, Gordon Royle · European Journal of Combinatorics · arXiv:1808.02051 · doi:10.1016/j.ejc.2020.103092

  Proves that the core of a cubelike graph inherits strong structural, spectral and group-theoretic properties forcing it to closely resemble a cubelike graph, and verifies the Nešetřil–Šámal conjecture for cubelike graphs whose core has at most 32 vertices (so any counterexample needs ≥128 vertices with a core on ≥64 vertices).

• partial Cayley graphs on elementary abelian groups of extreme degree have complete cores (2025)
  Guang Rao, Colin Tan · arXiv preprint · arXiv:2501.18297

  Shows that for any prime $p$, a Cayley graph on an elementary abelian $p$-group whose degree is strictly less than $5$ or at least $5$ less than the number of vertices has a complete core induced by an $\mathbb{F}_p$-subspace, settling the Nešetřil–Šámal core question for these extreme-degree cases (and showing the bound is sharp via the folded 5-cube).

Reviewer notes. The general conjecture for arbitrary abelian $M$ (and even the cubelike $M=\mathbb{Z}_2$ case) is still open: no full proof or counterexample was found. The two cited papers give the strongest known partial progress (small-core verification and extreme-degree cases). The ScienceDirect page for the journal version returned HTTP 403, so the journal/year/DOI for the Mančinska–Pivotto–Roberson–Royle paper were verified instead via the UWA research repository (European J. Combin. 87, 2020, art. 103092).

Auto-reviewed 2026-05-08 with claude-sonnet (subagent) (web search enabled).