TR-IIS-05-021    Fulltext

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.