TR-IIS-05-021
** ** Fulltext

**Generalized
Edge Coloring for Channel Assignment in Wireless
Networks**

Chun-Chen Hsu, Pangfeng
Liu, Da-Wei Wang, Jan-Jan Wu

**Abstract**

This paper introduces a new graph theory problem
called generalized edge coloring (g.e.c). g.e.c is similar to traditional edge
coloring, with the difference that a vertex can be adjacent to up to k edges
that share the same color. g.e.c. can be used to formulate the channel assignment
problem in multi-channel multi-interface wireless networks. We provide theoretical

analysis for this problem. Our theoretical findings can be useful for system
developers of wireless networks.

We show that when k = 3, there is no optimal solution. When k = 2 and the maximum
degree of the graph is no more than 4, or is a power of 2, we derive optimal
algorithms to find a g.e.c. Furthermore, if given one extra color, we can find
a g.e.c. that uses minimum number of edge colors for each vertex.