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₂: 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.