Keller Graph

The n-dimensional Keller graph, sometimes denoted G_n (e.g., Debroni et al. 2011), can be defined on a vertex set of 4^n elements (m_1,...,m_n) where each m_i 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 n=6.

Corrádi and Szabó (1990) showed that a clique in this graph has size at most 2^n, and furthermore that if there exists a clique of size 2^n, 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 n<=6 by mathematical proof (Perron 1940) and false for at least n=8, 10, and 12, with the smallest open case being n=7, where disproof for dimensions n>=8 has been via construction of maximum cliques of size 2^n. Recently, Debroni et al. (2011) determined the clique number for G_7 as 124 but, as noted above, the absence of a clique of size 2^n does not establish the theorem in dimension n.

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

The chromatic, fractional chromatic numbers, and independence number of G_n are all 2^n for n>2 (W. Myrvold; pers. comm., S. Wagon, Jan. 22, 2013). The independence number for n=1, 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 Delta.

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

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.

See also

Clebsch Graph, Keller's Conjecture, Maximum Clique

Explore with Wolfram|Alpha


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 n-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."

Cite this as:

Weisstein, Eric W. "Keller Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications