Up

Cubelike graphs

A cubelike graph is a Cayley graph where the underlying group G is the elementary Abelian group of order 2m. Thus, the vertex set is G, and two vertices are adjacent when their difference is in S, the difference set of the graph.

For example, the Clebsch graph is cubelike.

Spectrum

A cubelike graph has integral spectrum (Lovász).

Chromatic number

A cubelike graph does not have chromatic number 3 (Payan). Examples of cubelike graphs with chromatic numbers 2t (for any t), 6 and 7 are known. It is unknown whether there exists a cubelike graph with chromatic number 5.

Cubelike hull

Let X be an arbitrary graph, and let X0 resp. X1 be the graphs that have as vertex set the collection of subsets of the vertex set of X of even (odd) size, where two subsets are adjacent when their symmetric difference is an edge of X. Then X0 and X1 are isomorphic.

Put H(X) = X1 and call it the cubelike hull of X. The graph H(X) is cubelike, and contains X as an induced subgraph.

Any homomorphism φ : X → C, where C is cubelike, extends to a homomorphism ψ : H(X) → C. This gives information on the chromatic number of C.

For example, if C is not bipartite, then it contains an odd cycle X, but for a (2d+1)-cycle X the cubelike hull H(X) is the folded (2d+1)-cube which has chromatic number 4. This proves Payan's theorem.

The cubelike hull H(X) of the complete graph Kn is the halved n-cube. Thus, if a cubelike graph C contains K5, then there is a homomorphism from H(K5), the Clebsch graph, into C, and hence C has chromatic number at least 8.

If X is cubelike, then X → H(X) → X, so that χ(H(X)) = χ(X).

Independence number and chromatic number of halved cubes

More generally, the chromatic number χ(H(Kn)) satisfies χ(H(Kn)) ≥ 2n–1 / α(H(Kn)), and α(H(Kn)) equals the size of the largest binary code of word length n and minimum distance 4. This explains the lower bounds in the table below. (For the bounds on codes, see, e.g., this table.)

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
α 1 1 1 2 2 4 8 16 20 40 72 144 256 512 1024 2048
χ 1 2 4 4 8 8 8 8 13-14 13-15 15-16 15-16 16 16 16 16

Clearly the χ(H(Kn)) are a non-decreasing function of n.

If n is a power of 2, then Kn is cubelike, so that χ(H(Kn)) = χ(Kn) = n for these n.

The upper bounds 14 and 15 for χ(H(K9)) and χ(H(K10)) are due to Stefan Hougardy and Gordon Royle.

Projective formulation

The difference set S can be viewed as subset of the hyperplane PG(m–1,2) at infinity of the affine geometry G. This means that we have a (monotone) function "chromatic number" on the subsets of a projective space over GF(2). This number is 1 for the empty set, and 2 for sets contained in the complement of a hyperplane (and only for these), and never 3.
Proof: Suppose χ=2 and we have color classes A and B. Let X be the hyperplane PG(m–1,2) at infinity. Since A+s=B and B+s=A for any s in S, every even sum of elements of S is in X\S. Let Y be the subspace of X spanned by S. Then X\S contains the hyperplane of Y consisting of even sums of points in S, and hence X\S contains a hyperplane of X.
The chromatic number of the union of two sets is at most the product of the chromatic numbers of both sets.

If S is disjoint from a subspace T of projective dimension t–1, then the partition of G determined by T (into t-dimensional flats with T at infinity) provides a coloring with 2m–t colors.

For m < 5 the chromatic number only takes the values 1, 2, 4, 8, 16. In PG(4,2), a nondegenerate quadric S has chromatic number 7. For example, consider the quadric Q(x) = Σxi2 + Σxjxk (summed over all i and j < k) with nucleus (radical) {11111} (where 11111 stands for (1,1,1,1,1)). The isotropic points are the binary vectors of weights 3 and 4. A 7-coloring of G is given by the six balls of radius 1 around the vectors 11000, 10100, 00011, 01110, 01101, 10011 and the pair {00000,11111}. It is easy to check that there is no 6-coloring.

In PG(4,2), S has chromatic number at most 4 if and only if S is contained in the complement of a plane [Blokhuis]. (Indeed, suppose χ(S) ≤ 4 while S meets all planes. A color with a monochromatic plane in AG(5,2) colors only these four points, otherwise S would miss a plane. For every color without monochromatic plane all pairs of points with that color determine a different direction, so if the colorclass has size k, we find (k choose 2) points outside S, and k ≤ 7 since S contains more than 3 points. So four colors do not suffice to color the 32 points of AG(5,2).)

References

M.R. Best & A.E. Brouwer, The triply shortened binary Hamming code is optimal, Discrete Math. 17 (1977) 235-245.

C. Payan, On the Chromatic Number of Cube-like Graphs, Discrete Math. 103 (1992) 271-277.

G. Royle, Coloring cubelike graphs, PDF.

G.M. Ziegler, Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk problem in low dimensions, Springer LNCS, Computational Discrete Mathematics, 2001, pp. 159-171.