凯勒图

n 维凯勒图，有时记为 (例如，Debroni et al. 2011)，可以定义在 个元素的顶点集 上，其中每个 为 0、1、2 或 3，并且当两个顶点在至少两个坐标上不同，且在至少一个位置标签的差为 2（模 4）时，它们是相邻的。

这些图为凯勒猜想提供了一个方便的图论公式，并被广泛用于测试最大团算法（Myrvold 和 Fowler，Debroni 2011），因为即使对于 ，大多数启发式团算法也达不到正确的最大团阶数。

Corrádi 和 Szabó (1990) 表明，此图中的团的大小最多为 ，并且进一步表明，如果存在大小为 的团，则凯勒猜想在该维度上是错误的。然而，请注意，这种团的不存在并不一定意味着猜想的正确性，仅意味着对于坐标为整数或半整数的超立方体不存在反例（Debroni et al. 2011）。通过数学证明（Perron 1940），已知凯勒猜想对于 是成立的，并且对于至少 、10 和 12 是错误的，最小的未解决情况是 ，其中维度 的反证是通过构造大小为 的最大团来实现的。最近，Debroni et al. (2011) 确定了 团数 为 为 124，但是，如上所述，大小为 的团的缺失并不能在维度 中确立该定理。

凯勒图 (n=1, 2, ...) 的团数由 1, 2, 5, 12, 28, 60, 124, 256, ... 给出 (OEIS A202604)。

对于 ，凯勒图 的色数、分数色数和独立数均为 (W. Myrvold; 私人通讯，S. Wagon，2013 年 1 月 22 日)。对于 , 2, ...，独立数明确地为 4, 5, 8, 16, 32, 64, 128, 256, ... (OEIS A258935)。

Jarnicki et al. 2017 表明，所有凯勒图都是 1 类图，即边色数等于它们的最大顶点度 。

Fung (2011) 给出了凯勒图 , , ... 的 Lovász 数，分别为 4、6、28/3、、、....

所有连通的凯勒图都是哈密顿图 (W. Myrvold; 私人通讯，S. Wagon，2013 年 1 月 23 日) 和 哈密顿连通图 (私人通讯，S. Wagon，2013 年 1 月 24 日)。

特殊情况总结在下表中，其中 2-凯勒图（同构于 Clebsch 图）的情况的构造在上面进行了说明。

	图
1	4-空图
2	克莱布什图