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).
The chromatic, fractional chromatic numbers, and independence number of are all for (W. Myrvold; pers. comm., S. Wagon, Jan. 22, 2013). The independence number for , 2, ... are explicitly 4, 5, 8, 16, 32, 64, 128, 256, ... (OEIS A258935).
Jarnicki et al. 2017 showed that all Keller graphs are class 1, i.e., have edge chromatic number equal to their maximum vertex degree .
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.
graph | |
1 | 4-empty graph |
2 | Clebsch graph |