f2lk6wf90d's blog

Coloring a hypercube graph
By f2lk6wf90d, history, 7 years ago, In English

When is it possible to color the vertices of a hypercube graph Qk with k colors, such that for every vertex v, the colors of its adjacent vertices are pairwise distinct?
Example for Q2: 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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Every hypercube graph is bipartite (Source : Wiki). Thus, QK IS K colourable.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you provide an example for Q3? I tried bruteforcing the solution but I can't find an answer.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Color all vertices black and white in the usual bipartite way, then color an arbitrary vertex red?

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 of v have different colors", which is f2lk6wf90d's definition. You certainly need at least k colors to color Qk in the latter way, because every vertex has k neighbors.

    → Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

If n is a power of two, one can paint vertex (a0, a1, ..., an - 1) with color

On the other hand, let n equal 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.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +30 Vote: I do not like it

    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, 2n. This is only possible if n is a power of two, so your solution is complete.

    Edit in case anyone wants the counting argument written down: Let xi be the number of ordered pairs (v, w) such that v and w are neighbors and w has color i, and let ci be the total number of vertices of color i in the graph. Then, by fixing a vertex w of color i (ci options), there are n choices for v, so xi = nci. On the other hand, every vertex v (2n options) has exactly one neighbor of a given color i, so by fixing v first we have xi = 2n. So 2n = nci for every color i.

    → Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply