For example, the Clebsch graph is cubelike.

Put H(X) = X_{1} 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 K_{n}
is the halved n-cube. Thus, if a cubelike graph C contains K_{5},
then there is a homomorphism from H(K_{5}), 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).

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(K_{n})) are a non-decreasing function of n.

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

The upper bounds 14 and 15 for χ(H(K_{9})) and
χ(H(K_{10})) are due to Stefan Hougardy and Gordon Royle.

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 2^{m–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) = Σx_{i}^{2} + Σx_{j}x_{k}
(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).)

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.