The Application Of Lovasz Local Lemma In Distance-2 Coloring Problems

For the problem of channel assignment in radio networks, assigning time s-lots to nodes or links can be modeled as distance-2 vertex coloring and distance-2 edge coloring (also called strong edge coloring). A distance-2 vertex coloring of a graph is a coloring of the vertices such that any two vertices with distance at most 2 receive distinct colors. And a strong edge coloring is an assignment of colors to the edges of the graph such that for every color, the set of edges that are assigned the color forms an induced matching in the graphs. The distance-2 coloring problems are known to be NP-complete for some special graphs. There are few algorithmic results of the problems in a general graph so far. The Lovasz Local Lemma (LLL) is a significant result in probability theory that states the probability that none of a set of bad events happens is nonzero. In this paper,by the application of Lovasz Local Lemma,we state some algorithmic results of the distance-2 vertex coloring and strong edge coloring problems in a general graph including undirected and directed graph.