An undirected routing problem is a pair (G, R) where G and R are undirected graphs such that V(G) = V(R). A solution to an undirected routing problem (G, R) is a set P of undirected paths of G such that, for each edge {u, v} of R, P contains a path between u and v. We say that a set of paths P is k-colorable if each path of P can be colored by one of the k colors so that the paths of the same color are edge-disjoint (each edge of G appears at most once in the paths of each single color). Let Q n  denote the n-dimensional hypercube, for arbitrary n ≥ 1. We show that a routing problem (Q n , R) always admits a four-colorable solution when R is a matching, i.e., its maximum degree is one.
['Qian-Ping Gu', 'Hisao Tamaki']
Multi-Color Routing in the Undirected Hypercube