Radio Coloring on:
[Wikipedia]
[Google]
[Amazon]
In
In graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a branch of mathematics, a radio coloring of an undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
is a form of graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
in which one assigns positive integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
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 , under a different name, -labeling. It was called radio coloring by Frank Harary
Frank Harary (March 11, 1921 – January 4, 2005) was an American mathematician, who specialized in graph theory. He was widely recognized as one of the "fathers" of modern graph theory.
Harary was a master of clear exposition and, together with ...
because it models the problem of channel assignment in radio broadcasting
Radio broadcasting is transmission of audio (sound), sometimes with related metadata, by radio waves to radio receivers belonging to a public audience. In terrestrial radio broadcasting the radio waves are broadcast by a land-based radio ...
, while avoiding electromagnetic interference
Electromagnetic interference (EMI), also called radio-frequency interference (RFI) when in the radio frequency spectrum, is a disturbance generated by an external source that affects an electrical circuit by electromagnetic induction, electros ...
between radio stations that are near each other both in the graph and in their assigned channel frequencies.
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.. See in particular Section 3, "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 isNP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
, even when restricted to planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
s, split graph
In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by .
A split graph may have m ...
s, or the complements of bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
s. However it is solvable in polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
for trees
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
and cograph
In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...
s. 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 -vertex graph can range from 1 to ,almost all
In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the math ...
-vertex graphs have radio coloring number exactly . This is because these graphs almost always have diameter
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...
at least two (forcing all vertices to have distinct colors, and forcing the radio coloring number to be at least ) but they also almost always have a Hamiltonian path
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
in the complement graph
In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a ...
. Consecutive vertices in this path can be assigned consecutive colors, allowing a radio coloring to avoid skipping any numbers..
References
{{reflist Computational problems in graph theory Extensions and generalizations of graphs Graph coloring NP-complete problems NP-hard problems Radio resource management