Multicolor Routing in the Undirected Hypercube Qian-Ping Gu$^*$ and Hisao Tamaki$^{**}$ \vskip 0.2in $*$The University of Aizu Aizu-Wakamatsu, Fukushima, 965-8580 Japan Email: qian@u-aizu.ac.jp $**$Department of Computer Science, Meiji University 1-1-1 Higashimita, Tamaku, Kawasaki, 214 Japan E-mail: tamaki@cs.meiji.ac.jp Abstract: An {\em undirected routing problem} is a pair $(G, R)$ where $G$ is an undirected graph and $R$ is an undirected multigraph such that $V(G) = V(R)$. A {\em solution} to an undirected routing problem $(G, R)$ is a collection $P$ of undirected paths of $G$ (possibly containing multiple occurrences of the same path) such that edges of $R$ are in one-to-one correspondence with the paths of $P$, with the path corresponding to edge $\{u, v\}$ connecting $u$ and $v$. We say that a collection 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). In the circuit-switched routing context, and in optical network applications in particular, it is desirable to find a solution to a routing problem that is colorable with as few colors as possible. Let $Q_n$ denote the $n$-dimensional hypercube, for arbitrary $n \geq 1$. We show that a routing problem $(Q_n, R)$ always admits a $4d$-colorable solution where $d$ is the maximum vertex degree of $R$. %The previous bound is 16-colors for $d\leq 2$ %given by Aumann and Rabani [SODA95, pages 567-576]. %Our result improves over the previous one by a factor %of two for $d=2$ and of four for $d=1$. This improves over the $16\lceil d/2\rceil$-color result which is implicit in the previous work of Aumann and Rabani [SODA95, pages 567-576]. Since, for any positive $d$, there is a multigraph $R$ of degree $d$ such that any solution to $(Q_n, R)$ requires at least $d$ colors, our result is tight up to a factor of four. In fact, when $d = 1$, it is tight up to a factor of two, since there is a graph of degree one (the antipodal matching) that requires two colors. Key words: multicolor routing, edge-disjoint paths, algorithm, circuit-switched network