Generalization of an edge coloring of graphs and channel
assignment problem on multi-hop wireless networks
Hiroshi Tamura 1, Kazuyuki Miyakita 2, Keisuke Nakano 2, Masakazu Sengoku 2 and Shoji Shinoda 3
11

Faculty of Science and Engineering, Chuo University, Japan
2
Niigata University, Japan, 3 Waseda University, Japan

Introduction

Multi-hop wireless networks [1] are autonomous systems ofmobile nodes connected by wireless links and consist of nodes
and wireless links. The nodes are classified into two kinds: one
is a mobile terminal such as mobile phone, personal computer,handheld computer, Personal Digital Assistant (PDA) and so on,each of which has a router communication function for otherterminals and the other is a special terminal that acts only as arouter for mobile terminals and has a long-life or a permanent
battery(Fig.1). Such multi-hop wireless networks are useful invarious applications when cellular infrastructure is neither
available nor realistic or when ubiquitous communication
services are required without the presence or use of a fixed
infrastructure.
For multi-hop wireless networks, we assign channels tocommunication between two terminals. This is a kind of edge
coloring problem in graph theory. In the previous paper[2], wedefined a new edge coloring problem called middle edge
coloring and discussed the property of the coloring. In this paper,
we generalize the coloring and consider the meaning of thegeneralization.

The above two edge colorings are well-known. The following
coloring are defined in [2].
[Definition.3] Let G be an undirected graph. If an assignment ofcolors to edges of G satisfies the following conditions, thecoloring is called a middle edge coloring.
1) The assignment of colors is a conventional edge coloring.
2) Let (y,z) be an edge of G and be assigned color B. If an edge(x,y) and (z,u) are assigned color A(not B), x and u is notincident to edges assigned color B
Clearly, any middle edge coloring is a conventional edge
coloring, and any strong edge coloring is a middle edge coloring.
So, we call this coloring “middle” edge coloring.
3A generalization of the middle edge coloring
The middle edge coloring prohibits the following coloring.

Fig.2 A coloring which is not middle edge coloring.
This is a coloring using two colors. So, we call this coloring
two-alternate coloring.
So, a natural generalization of n-alternate coloring is asfollows[Definition.4] Let P2n be a path whose length is 2n. The assigned
colors to edges of P2n are A1,A2,…,An, A1,A2,…,An sequentially.
This coloring is called n-alternate coloring.
Using the definition above, we define a new coloring.
[Definition.5] For a natural number n, an edge coloring that notinclude t-alternate coloring for any t ( ≤ n) is called n-seg
coloring.

Fig.1 Multi-hop wireless network.

2Preliminary

In this paper, we adopt undirected graphs as a model ofmulti-hop wireless networks. First, we define some terms ofgraph theory.
[Definition.1] Let G be an undirected graph. A conventionaledge coloring of G is an assignment of colors to edges of G suchthat every two adjacent edges are assigned different colors.
[Definition.2] Let G be an undirected graph. A strong edge
coloring of G is an assignment of colors to edges of G such thatevery two edges of distance at most two are assigned different
colors. The distance of two edges is at most two means theedges are adjacent, or there is an edge between them.

€Clearly, any 1-seg coloring is a conventional coloring. So, nseg coloring is a generalization of the conventional edge€coloring.
n-alternate coloring and n-seg coloring are simple
expansion. However, there is the following interesting property.
[Property 1] Let P2n be a path whose vertices v0,v1,…,v2n andedges are e1,e2,…,e2n sequentially and assigned the distance d(ei)of edge ei for any ei. Moreover, P2n is assigned n-alternate
coloring. For 1 ≤ i ≤ n , Let edge (vi-1,vi) be assigned color Aand (vj,vj+1) be also assigned color A. We define
ratio(vi)=d(vi.vj)/d(vi-1,vi),
where, d(vi,vj) is the distance between vertex vi and vj.
For n ≤ i ≤ 2n −1, Let edge (vi,vi+1) be assigned color A and€j-1,vj) be also assigned color A. We define(vratio(vi)=d(vi.vj)/d(vi,vi+1).
Then,minratio(P2n)={ratio(v) | v is in P2n} is not greater than n-1.

Fig.3 3-altanate coloring for P6.
We explain the property using Fig.3. In Fig.3, a number on eachedge represents the distanse of the edge and a letter under eachedge represents the assigned color to the edge.
The edges (v0,v1) and (v3,v4) are assigned color A. Andd(v0,v1)=1, d(v1,v3)=2+2=4Therefore ratio(v1)=4/1=4. Other values are the following.
ratio(v2)=(2+4)/2=3ratio(v3)=(4+3)/2=3.5
ratio(v3)=(2+2)/4=1ratio(v4)=(2+4)/3=2ratio(v5)=(4+3)/1=7
About the middle vertex v3 of the path, we calculate ratio(v3)twice. In this case, minratio(P6) is the following.
minratio(P6)=min{4, 3, 3.5, 1, 2, 7}=1<n-1(=2).
In case of same distance for each edge, minratio(P2n)=n-1. So,
the value n-1 is critical.
4

Generalization of n-seg coloring

In the previous section, we define n-seg coloring. However,the definition prohibits coloring limited very much. Here, we
generalize the prohibited coloring.
[Definition.6] For graph G. n-Gseg coloring of G is an edge
coloring satisfying the following condition.
For any path P2t whose length is 2t (1 ≤ t ≤ n), on G, thenumber of colors on P2t is greater than or equal to t+1.

€€Fig.4 A coloring to Path P6.
We explain the coloring. In Fig.4, the coloring of P6 is a 3seg coloring. Because, there is not 2-altanate coloring and 3altanate coloring in P6. However, the coloring is not 3-Gseg
coloring. Because the number of colors on P6 is three.
Conversely, n-Gseg coloring is obviously n-seg coloring.
In case of n=1, the number of colors on P2 is 2. Therefore,
conventional edge coloring is equivalent to 1-Gseg coloring.
In case of n=2, the number of colors on P2 is 2, and thenumber of colors on P4 is 3 or 4. Therefore, middle edge
coloring is equivalent to 2-Gseg coloring.
Every strong edge coloring is 2-Gseg coloring. However
every 2-Gseg coloring is not always strong edge coloring.
In the previous paper, we show if a coloring is not middle edge
coloring then the coloring is not applied to channel assignmentof multi-hop wireless networks. However, in case of Gseg
coloring, the property above does not hold. For example, weconsider the following case.

Fig.5 A coloring which is not Gseg coloring.

This coloring is not 3-Gseg coloring. However, this coloring canbe applied to channel assignment of multi-hop wireless network
because the distance (v3,v4) is very large.
In Fig.4, color C is assigned only to (v3,v4). This fact is very
important for consideration of channel assignment. Because thecolor assigned only to one edge has nothing to do with thecochannel interference. Therefore we ignore the edge and thecoloring to the edge in consideration with cochannelinterferences. Therefore, we ignore the edge and the coloring ofthe edge when we consider the cochannel interference. As aresult,Fig.6 The coloring that is changed.
the coloring is as Fig.6. This coloring uses two colors and this is2-Gseg coloring.
When we apply edge coloring to channel assignment, thefollowing step is necessary.
1) We assign a color to every edge.
2) We ignore the color that is used only once.
3) We consider whether coloring is appropriate.
Using this model, we suppose an algorithm and evaluate it bycomputer simulation.
References[1] C. E. Perkins, Ad Hoc Networking, Addison-Wesley, 2001.
[2] Hiroshi Tamura, Masakazu Sengoku and Shoji Shinoda, On an Edge
Coloring between Conventional Edge Coloring and Strong Edge
Coloring for Wireless Communications, Proc. 2011 Int. Tech. Conf.
Circuits/Systems, Computers and Comm. (ITC-CSCC2011), pp.57-60,
2011.