 | ||
In graph theory, a branch of mathematics, a radio coloring of an undirected graph is a form of graph coloring in which one assigns positive integer labels to the graphs such that the labels of adjacent vertices differ by at least two, and the labels of vertices at distance two from each other differ by at least one. Radio coloring was first studied by Griggs & Yeh (1992), under a different name, L(2,1)-labeling. It was called radio coloring by Frank Harary because it models the problem of channel assignment in radio broadcasting, while avoiding electromagnetic interference between radio stations that are near each other both in the graph and in their assigned channel frequencies.
Contents
The span of a radio coloring is its maximum label, and the radio coloring number of a graph is the smallest possible span of a radio coloring. For instance, the graph consisting of two vertices with a single edge has radio coloring number 3: it has a radio coloring with one vertex labeled 1 and the other labeled 3, but it is not possible for a radio coloring of this graph to use only the labels 1 and 2.
Computational complexity
Finding a radio coloring with a given (or minimum) span is NP-complete, even when restricted to planar graphs, split graphs, or the complements of bipartite graphs. However it is solvable in polynomial time for trees and cographs. For arbitrary graphs, it can be solved in singly-exponential time, significantly faster than a brute-force search through all possible colorings.
Other properties
Although the radio coloring number of an n-vertex graph can range from 1 to 2n − 1, almost all n-vertex graphs have radio coloring number exactly n.