When is it possible to color the vertices of a hypercube graph *Q*_{k} with *k* colors, such that for every vertex *v*, the colors of its adjacent vertices are pairwise distinct?

Example for *Q*_{2}: We can color any two adjacent vertices with the same color, and color the other two vertices with another color. Then for every vertex, its neighbors will be colored differently.

Every hypercube graph is bipartite (Source : Wiki). Thus,

Q_{K}ISKcolourable.Can you provide an example for

Q_{3}? I tried bruteforcing the solution but I can't find an answer.Color all vertices black and white in the usual bipartite way, then color an arbitrary vertex red?

The restriction on the coloring is not the standard one. When you say "bipartite", that means "can be colored using two colors so that no edge is monochromatic". This is different from "can be colored using two colors such that, for any

v, all neighbors ofvhave different colors", which is f2lk6wf90d's definition. You certainly need at leastkcolors to colorQ_{k}in the latter way, because every vertex haskneighbors.If

nis a power of two, one can paint vertex (a_{0},a_{1}, ...,a_{n - 1}) with colorOn the other hand, let

nequal 3. We can assume wlog that (0, 0, 0) and (0, 0, 1) have color 0, (0, 1, 0) has color 1 and (0, 0, 1) has color 2. Consider (0, 1, 1). Two of its neighbors have colors 0 and 1, hence (1, 1, 1) has color 2. Then two of (1, 0, 1)'s neighbors have color 2, which is a contradiction.Unfortunately, I can't generalize it yet.

Since the graph is regular, a counting argument shows that all color classes must have the same size, so the number of colors,

n, must divide the number of vertices, 2^{n}. This is only possible ifnis a power of two, so your solution is complete.Edit in case anyone wants the counting argument written down: Let

x_{i}be the number of ordered pairs (v,w) such thatvandware neighbors andwhas color i, and letc_{i}be the total number of vertices of coloriin the graph. Then, by fixing a vertexwof colori(c_{i}options), there arenchoices forv, sox_{i}=nc_{i}. On the other hand, every vertexv(2^{n}options) has exactly one neighbor of a given colori, so by fixingvfirst we havex_{i}= 2^{n}. So 2^{n}=nc_{i}for every colori.Hi i solved this problem with 2k colors i don't know it helps or not.

You can show each vertex of Qk with a k-bit number.

Now the problem is to color the numbers with 2k colors in a way that any two numbers that have exactly 2 bit difference should have distinct color(this coloring solve at most 2 difference too).

Consider a number X. we know that X = 2^x1 + 2^x2 + .. 2^xm, color this number with (x1 + x2 + x3 + ... + xm) mod k.

For changing two bits and not changing the mod you have two change x and k-x else x=0,

now if we save the number of 1-bits from 0 to k/2 is even of odd, it will works.

the color of X is now (x1 + x2 + ... + xm) % k * (even(1) or odd(2) 1-bits from 0 to k/2)

thanks for reading.

Nice Idea