2-Lo al 4/3-Competitive Algorithm For Multi oloring Hexagonal Graphs

An important optimization problem in the design of ellular networks is to assign sets of frequen ies to transmitters to avoid una eptable interferen e. A ellular network is generally modeled as a subgraph of the innite triangular latti e. The distributed frequen y assignment problem an be abstra ted as a multi oloring problem on a weighted hexagonal graph, where the weight ve tor represents the number of alls to be assigned at verti es. In this paper we present a distributed algorithm for multi oloring hexagonal graphs using only the lo al lique number!(v) at ea h vertex v of the given hexagonal graph, whi h an be omputed from lo al information available at the vertex. We prove the algorithm uses no more than