| Abstract: | Motivated by the problem of designing large packet radio networks, we show that the Kautz and de Bruijn digraphs with in- and outdegree d have arc-chromatic index 2d. In order to do this, we introduce the concept of even 1-factorizations. An even 1-factor of a digraph is a spanning subgraph consisting of vertex disjoint loops and even cycles; an even 1-factorization is a partition of the arcs into even 1-factors. We prove that if a digraph admits an even 1-factorization, then so does its line digraph. (In fact, we show that the line digraph admits an even 1-factorization even under a weaker assumption discussed below.) As a consequence, we derive the above property of the Kautz and de Bruijn digraphs relevant to packet radio networks. © 1993 John Wiley & Sons, Inc. |
