Radio coloring

Radio coloring was first studied by Griggs & Yeh (1992), under a different name, L(2,1)-labeling.

[1][2] 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.

[1] 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.

[1][4] For arbitrary graphs, it can be solved in singly-exponential time, significantly faster than a brute-force search through all possible colorings.

[5][6] 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. This is because these graphs almost always have diameter at least two (forcing all vertices to have distinct colors, and forcing the radio coloring number to be at least n) but they also almost always have a Hamiltonian path in the complement graph.