The -dimensional Keller graph, sometimes denoted
(e.g., Debroni et al. 2011),
can be defined on a vertex set of elements where each is 0, 1, 2, or 3 and two vertices are adjacent if they differ
in at least two coordinates and in at least one position the difference in the labels
is 2 (modulo 4).

These graphs give a convenient graph theoretic formulation of Keller's conjecture and have been used extensively for testing maximum
clique algorithms (Myrvold and Fowler, Debroni 2011) since most heuristic clique
algorithms fall short of the correct maximum clique order even for .

Corrádi and Szabó (1990) showed that a clique in this graph has size at most ,
and furthermore that if there exists a clique of size , Keller's conjecture
is false in that dimension. However, note that the nonexistence of such a
clique does not necessarily imply the truth of the conjecture, only that no
counterexample exists with hypercubes whose coordinates are integers or half-integers
(Debroni et al. 2011). Keller's conjecture
is known to be true for
by mathematical proof (Perron 1940) and false for at least , 10, and 12, with the smallest open case being , where disproof for dimensions has been via construction of maximum cliques of size
. Recently, Debroni et al. (2011)
determined the clique number for as 124 but, as noted above, the absence of a clique of size
does not establish the theorem in
dimension .

The clique numbers for the Keller graphs with , 2, ... are given by 1, 2, 5, 12, 28, 60, 124, 256, ...
(OEIS A202604).

Fung (2011) gives the Lovász numbers of the Keller graphs ,
, ..., as 4, 6, 28/3, , ,
....

All connected Keller graphs are Hamiltonian (W. Myrvold; pers. comm., S. Wagon, Jan. 23, 2013) and Hamilton-connected
(pers. comm., S. Wagon, Jan. 24, 2013).

Special cases are summarized in the following table and where the construction in the case of the 2-Keller graph (which is isomorphic to the Clebsch
graph) is illustrated above.

Corrádi, K. and Szabó, S. "A Combinatorial Approach for Keller's Conjecture." Periodica Mathematica Hungarica. Journal
of the János Bolyai Math. Soc.21, 95-100, 1990.Debroni,
J.; Eblen, J. D.; Langston, M. A.; Shor, P.; Myrvold, W.; and Weerapurage,
D. "A Complete Resolution of the Keller Maximum Clique Problem." Proceedings
of the 22nd ACM-SIAM Symposium on Discrete Algorithms. pp. 129-135, 2011.Fung,
M. "The Lovász Number of the Keller Graphs." Master thesis. Universiteit
Leiden: Mathematisch Instituut, 2011.Jarnicki, W.; Myrvold, W.; Saltzman,
P.; and Wagon, S. "Properties, Proved and Conjectured, of Keller, Mycielski,
and Queen Graphs." To appear in Ars Math. Comtemp. 2017.Johnson,
D. S. and Trick, M. A. Cliques,
Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October
11-13, 1993. Boston, MA: Amer. Math. Soc., 1996.Lagarias, J. C.
and Shor, P. W. "Keller's Cube-Tiling Conjecture Is False in High Dimensions."
Bull. Amer. Math. Soc.27, 279-283, 1992.Mackey, J. "Cube
Tiling of Dimension Eight with No Facesharing." Disc. Comput. Geom.28,
275-279, 2002.Myrvold, W. and Fowler, P. W. "Fast Enumeration
of All Independent Sets up to Isomorphism." J. Comb. Math. Comb. Comput.85,
173-194, 2013.Peron, O. "Über lückenlose ausfüllung
des -dimensionalen raumes durch kongruente
würfel." Math. Z.46, 1-26 and 161-180, 1940.Sloane,
N. J. A. Sequences A202604 and A258935 in "The On-Line Encyclopedia of Integer
Sequences."