L(h, k)-coloring

One of the key topics in graph theory is graph coloring and in particular vertex coloring. Fascinating generalizations of the notion of graph coloring are motivated by problems of channel assignment in wireless communications,traffic phasing, fleet maintenance,task assignment, and other applications. Ordinary vertex colorings of graphs that assign different integers to adjacent vertices have the property that the fewest colors needed can always lie in an interval all of whose integers are assigned to some vertex. Such a special integer coloring is called L(h, k)-coloring or sometimes referred to as L(h, k)-labelling.

The L(h,k)-coloring was introduced by Griggs and Yeh to model a frequency assignment problem, where wireless receivers must be assigned frequencies without causing interference. A large body of research has developed through the years on L(h, k)-coloring problems. The aim of the L(h, k)-coloring problem is to minimize the span of the difference between the largest and the smallest used colors.

The L(h, k)-coloring problem has been intensively studied following many approaches and restricted to many special cases, concerning both the values of h and k and the considered classes of graphs. Most of that effort has been on two cases. They are the L(1,1) coloring and L(2,1) coloring. . When h=1 and k=0, it is the usual (proper) vertex coloring.

Definition

L(h, k) coloring in graph theory, is a (proper) vertex coloring of a graph G [G=(V,E)] such that adjacent vertices are labelled using colors at least h apart, and vertices having a common neighbour are labelled using colors at least k apart.

Alternative Definition

Given a graph G = (V, E) and two non negative integers h and k, an L(h, k)-labeling of a graph G, is a function c from the vertex set V to a set of non-negative integers called colors such that for all x, y ∈ V(G),

(i) |c(x) - c(y)| ≥ h whenever distance (x,y) = 1 and (ii) |c(x) - c(y)| ≥ k whenever distance(x,y) = 2.

Brief

The term L(h, k) coloring was introduced by Griggs and Yeh in the special case h = 2 and k = 1 in connection with the problem of assigning frequencies in a multi hop radio network (for a survey on the class of frequency assignment problems. Although it has been previously mentioned by Roberts in his summary on T-coloring and investigated in the special case h = 1 and k = 1 as a combinatorial problem and hence without any reference to channel assignment After its definition, the L(h, k)- coloring has been used to model several problems, for certain values of h and k. One example among them is Bertossi and Bonuccelli introduced a kind of integer "control code" assignment in packet radio networks to avoid hidden collisions, equivalent to the L(0, 1)-coloring problem. Channel assignment in optical cluster based networks can be seen either as the L(0, 1)-coloring problem or as the L(1, 1)-coloring problem,depending on the fact that the clusters can contain one ore more vertex. More in general, channel assignment problems with a channel defined as a frequency, a time slot, a control code, etc., can be modeled by an L(h, k)-coloring problem, for convenient values of h and k. Besides the practical aspects, also purely theoretical questions are very interesting. These are only some reasons why there is considerable literature devoted to the study of the L(h, k) coloring problem following many different approaches including graph theory and combinatorics, simulated annealing, genetic algorithms, and neural networks.

the L(h,k)-labelling problem of products of complete graphs is considered (h ≥ k) and the following exact results are given, where 2 ≤ n < m:\\

-λ_h,k (K _{n Χ m}) = (m-1)h+(n-1)k, if h/k > n.\\

-λ_h,k (K _{n Χ m}) = (mn-1)k, if h/k ≤ n.\\

-λ_h,k (K _{n Χ m}) = (n-1)h+(2n-1)k, if h/k > n-1.\\

-λ_h,k (K _{n Χ m}) = (n*n-1)h, if h/k ≤ n-1.\\

Georges and Mauro provides a bound on the λ_h,k number for general h and k for some trees of maximum degree Δ ≤ h/k.Later, the same authors investigate L _h,k labellings of trees for h ≥ k and Δ ≥ 3.

Terminology

An L(2,1)-coloring, c, of P₄ is given along with another L(2,1)-coloring, c'. It is observed that c'-span is same as the L-span.

Span

For some non negative integers h and k, an L(h,k)-coloring function 'c' of a graph G is chosen. The Span of c which is also called c-span is defined as max{|c(u)-c(v)|} for every pair of vertices u,v of G. It is denoted as λ_h,k(c).

L-span

The L-span or λ_h,k-number of G is defined as min{λ_h,k(c)}. Here the minimum is taken over all L(h,k)-colorings c of G.

First-Fit

The First-Fit algorithm is one of the simplest coloring strategies. Processing the vertices in an arbitrary order, each vertex is assigned the smallest color compatible with its neighborhood. For the L(h, k)-coloring problem, satisfying the distance constraints to the previously colored neighbors as well as previously colored vertices of distance two. .

Results

Minimum span

The minimum span of an L(h,k)-coloring of G is bounded below by,

             λh,k(G) ≤ (Δ - 1). k + h + 1 

Performance ratio ρ_A

Let λ_h,k-number of G denote the minimum span of a L(h, k)-coloring of a graph G. The performance ratio ρ_A of an L(h, k)-coloring algorithm A is the maximum ratio between the maximum and minimum spans, i.e.,

                   ρA =ρA(G) = max|V (G)|=n  A(G)/ λh,k 

The span of a First-Fit

Let d₂(v) be the number of neighbors of distance-2 from a vertex v and ∆₂ = {max (v) d₂(v) ≤ ∆(∆ − 1)} be the maximum of these values of vertices in the graph. The span of a First-Fit L(h, k)-coloring of a graph G is at most

 FF(G) ≤ {max v∈V [ d2(v) · (2k − 1) + d(v) · (2h − 1)] ≤ ∆2 · (2k − 1) + ∆ · (2h − 1) + 1}

Also,

      FF(G) ≤ n · h 

Types

The most widely studied topic in L(h,k) coloring is when h=2 and k=1 known as L(2,1) coloring. As mentioned earlier Griggs and Yeh were among the first to work upon L(2,1) coloring. We are familiar with L(1,0)-coloring of a graph G which is nothing but the proper coloring of G.

L(1,0) coloring

File:Proper coloring.png

An L(1,0)-coloring of C₅

Main article: Proper coloring

An L(1,0)-coloring of a graph is the same as a proper coloring for the graph. In a proper coloring of a graph, the adjacent vertices are given different colors. So, here, in L(1,0)-coloring, the vertices that are adjacent must be given labels or colors in such a way that they differ by at least one. The minimum number of colors required to color a graph in this way is called the chromatic number of the graph.

L(2,1)-coloring

Main article: L(2,1)-coloring

The channel assignment problem is the problem of efficiently assigning frequencies to radio transmitters located at various places such that communications do not interfere.In 1988, F. S. Roberts proposed (in a private communication with Griggs) the problem of efficiently assigning radio channels to transmitters at several locations, using nonnegative integers to represent channels, so that close locations receive different integers, and channels of very close locations are at least 2 apart. This evolved into the study of L(2,1)-coloring of a graph first studied by Griggs and Yeh

Definition

File:L(2,1)-coloring.png

Example of L(2,1)-coloring

An L(2,1)-coloring of a graph G is assigning colors to the vertices of the graph according to the L(h,k)-labeling. Adjacent vertices are colored in such a way that the labels must differ by at least 2. Also the vertices that are at a distance of two from each other are colored in a way that the labels must differ by at least 1. There is no restriction on coloring of vertices that are at a distance of 3 or more. The c-spans and L-span are defined for the L(2,1)-coloring as it was defined for the L(h,k)-coloring. The L-span or λ_2,1-number of G defined as min{λ_2,1(c)} is simply denoted as λ(G).

Alternative Definition

Given a graph G = (V, E) simple graph with a non-empty, finite vertex set and two non negative integers h and k, an L(2, 1)-labeling of a graph G, is a function 'c' from the vertex set V to a set of non-negative integers {0, 1, 2,...,k} where k ≥ 2 such that for all x, y ∈ V(G),

(i) |c(x) − c(y)| ≥ 2 for all xy ∈ E(G)and  (ii) |c(x) − c(y)| ≥ 1 whenever distance(u, v) = 2.

File:L(2,1)-coloring of star on 13 vertices.png

L(2,1)-coloring of a Star

An L(2,1)-coloring of C₁₀, where span is 4

Propositions

Let P_n be a path on n ≥ 5 vertices. Then,

                 λ(Pn) = 4

Let C_n be a cycle on n ≥ 3 vertices. Then,

                 λ(Cn) = 4

If T is a tree with maximum degree ∆ ≥ 1. Then,

                  ∆+1 ≤ λ(T) ≤ ∆+2.

In particular, the L(2,1)-coloring of a star, K_1,n is ∆+1.

Applications

Channel assignment

In recent years the comparative use of wireless communication services has been on the rise. But there is less availability of useful resources and also the cost of radio spectrum bandwidth is quite high. Therefore, the cellular network operators are finding ways to maximize spectrum efficiency. One of the ways by which this can be attained is the optimal frequency reuse. In this the same part of the radio spectrum is used in different locations of the network simultaneously using communication links . In this system any two pair of cells in the network can use the same channel simultaneously, or not. For networks based on frequency division or time division the amount of interference between two channels that are near to each other in the spectrum is considerably different from that between channels that are far apart from each other. Therefore, the distance between cells using channels close together must be greater than the distance between cells that use channels which are far away from each other. A graph model can be used to solve the channel assignment problem. A graph is taken in which the vertices represents the cells or their base stations in the network. The edges represent the cell adjacency. Different algorithms are used to reach the optimal solution to our problem. The distances between the cells are noted and are measured in integral values. Therefore, the L(h,k)-coloring has a significant role to play in finding the optimal solution for the above-mentioned problem.

Optical Networks

One of the ways to meet the increasing demands of high bandwidth is by using optical networks. In the process of connecting individual stations, an optical passive star interconnection with wavelength division multiplexing(WDM) has been considered. The WDM links are so easier to build and thus are operational precursors to WDM networks with multiple nodes . However, in a single passive star configuration, the size of the network is restricted by the number of separable and coupled wavelengths and the power dispersion. The main aim is to enhance the scalability of optical networks by using multi-star configuration. In such networks, a virtual topology is embedded on the physical topology by identifying the patterns in connectivity between different stations in the network. In the network, a transmitter sends its signal to a group of receivers which are determined by specific virtual topology. The routing algorithm uses the virtual topology to minimize the network delay and maximize the network output. Some of the constructions which are appropriate are mesh networks and hyper-cube networks.

A discrete broadcast-select multi-domain WDM network was proposed to achieve scalability and reconfigurable partitioning on various virtual topologies. The network consists of nodes which are grouped together to form clusters. These clusters are interconnected by using one of the virtual topologies. Inside the clusters, in addition to the regular inter-cluster links, the nodes are connected to themselves by cluster self links to establish intra-cluster connectivity. The problem in this type of network involving clusters of nodes is to assign conflict-free channel sets to every cluster by minimizing the number of channel sets. Peng-Jun Wan optimized the conflict free channel assignments in an embedding of a cluster based hypercube. In that process, the problem was transformed into a graph theoretical model using graph coloring. The problem was solved using a vertex coloring of distance two or less in the hypercube, which is essentially related to L(h, k)-coloring.

See also

• Defective coloring
• Harmonious coloring
• Radio coloring
• Sum coloring
• Interval edge coloring
• Incidence coloring

References

• Griggs, J. R.; Yeh, R. K. (1992), "Labelling graphs with a condition at distance 2", SIAM Journal on Discrete Mathematics, 5 (4): 586–595, doi:10.1137/0405048
• Chartrand, Gary; Zhang, Ping (2009), "14. Colorings, Distance, and Domination", Chromatic Graph Theory, CRC Press, pp. 397–438
• Roberts, Fred S. (25 November 1991), "T-colorings of graphs", Discrete Mathematics, 93 (2–3): 229–245, doi:10.1016/0012-365X(91)90258-4
• A.A, Bertossi; M.A, Bonuccelli (Aug 1995), "Code assignment for hidden terminal interference avoidance in multihop packet radio networks", Networking, IEEE/ACM Transactions, 3 (4): 441–449, doi:10.1109/90.413218
• Hong, Sungpyo (February 2000), Combinatorial & Computational Mathematics, Pohang,Republic of Korea: World Scientific, 2001, ISBN 9812799893
• R, Mathar; J, Mattfeld (1993), "Channel assignment in cellular radio networks", {IEEE} Transactions on Vehicular Technology, 42 (4): 647–656
• W.K, Lai,; G.G, Coghill (1996), "Channel assignment through evolutionary optimization", Vehicular Technology, IEEE Transactions, 45 (1): 91–96, doi:10.1109/25.481825{{citation}}: CS1 maint: extra punctuation (link) CS1 maint: multiple names: authors list (link)
• N, Funabikiy; Y, Takefuji (1992), "A neural network parallel algorithm for channel assignment problems in cellular radio networks", Vehicular Technology, IEEE Transactions, 41 (4): 430–437, doi:10.1109/25.182594
• Roberts, F (1988), Personal communication to J. Griggs
• Griggs, J. R.; Yeh, R. K. (1992), "Labelling graphs with a condition at distance 2", SIAM Journal on Discrete Mathematics, 5 (4): 586–595, doi:10.1137/0405048

• Halldorsson, Magnus M (2006), "Approximating the L(h, k)-labelling problem", Int. J. of Mobile Network Design and Innovation, 1 (2): 113–117, doi:10.1504/IJMNDI.2006.010813

• Laskar, Renu; Eyabi, Gilbert, "Holes in L(2, 1)-Coloring on Certain Classes of Graphs", AKCE International Journal of Graphs and Combinatorics, 6 (2): 329–339

• Katzela, I.; Naghshineh, M. (1996), "Channel assignment schemes for cellular mobile telecommunications: a comprehensive survey", IEEE Personal Communications, pp. 10–31
• Narayanan, L. (2001), "Channel assignment and graph multicoloring", Handbook of wireless networks and mobile computing, Wiley, ISBN 0-471-41902-8