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.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3821 |
| 3 | Benq | 3736 |
| 4 | Radewoosh | 3631 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3388 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 10.11.2024 12:10:34 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
Every hypercube graph is bipartite (Source : Wiki). Thus, QK IS K colourable.
Can you provide an example for Q3? 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 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.
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.
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.
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.