Radio coloring

Optimal (span-4) radio coloring of a 6-cycle

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

Radio coloring is closely related to the L(2,1)-labeling (or L(2,1)-coloring) problem first studied by Griggs & Yeh (1992); radio coloring uses labels starting from 1, while L(2,1)-labeling typically uses labels starting from 0. ^{[2] [3]} This means that a radio coloring can be transformed into an L(2,1)-labeling by simply subtracting 1 from the value at each vertex, and vice versa by adding 1. The two problems are essentially differ only by notation in most regards, and so are often considered the same problem.

The name "radio coloring" was introduced 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.

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

Relationship to other labeling problems

Radio coloring is part of a family of graph labeling problems. The L(2,1)-labeling problem is essentially equivalent to radio coloring, with the main difference being the starting index for labels (0 versus 1). This means that if a graph has L(2,1)-labeling number k, it has radio coloring number k + 1. ^[3]

Radio coloring should not be confused with radio labeling, which is a different problem where all vertices must receive distinct labels, and adjacent vertices must have labels that differ by at least 2. ^[2] In radio labeling, the constraint at distance two is automatically satisfied since all labels are distinct.

Results for specific graphs

Griggs and Yeh proved that for cycle graphs, the L(2,1)-labeling number is 4, which means the radio coloring number for cycles is 5. ^[3] For graphs of maximum degree Δ, they showed that the L(2,1)-labeling number is at most Δ² + 2Δ, meaning that the radio coloring number is at most Δ² + 2Δ + 1. ^[3]

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. ^{[2] [4]} However it is solvable in polynomial time for trees and cographs. ^{[2] [5]} For arbitrary graphs, it can be solved in singly-exponential time, significantly faster than a brute-force search through all possible colorings. ^{[6] [7]}

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. 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. Consecutive vertices in this path can be assigned consecutive colors, allowing a radio coloring to avoid skipping any numbers. ^[8]

See also

• L(h, k)-coloring
• List coloring
• Graph coloring

References

1. Chartrand, Gary; Zhang, Ping (2009). "14. Colorings, Distance, and Domination". Chromatic Graph Theory. CRC Press. pp. 397–438.
2. Broersma, Hajo (2005), "A general framework for coloring problems: old results, new results, and open problems" (PDF), Combinatorial geometry and graph theory (PDF), Lecture Notes in Comput. Sci., vol. 3330, Springer, Berlin, pp. 65–79, doi:10.1007/978-3-540-30540-8_7, ISBN   978-3-540-24401-1, MR   2172960 . See in particular Section 3, "Radio coloring".
3. Griggs, Jerrold R.; Yeh, Roger K. (1992), "Labelling graphs with a condition at distance 2" (PDF), SIAM Journal on Discrete Mathematics , 5 (4): 586–595, doi:10.1137/0405048, MR   1186826
4. Bodlaender, Hans L.; Kloks, Ton; Tan, Richard B.; van Leeuwen, Jan (2000), "λ-coloring of graphs", STACS 2000: 17th Annual Symposium on Theoretical Aspects of Computer Science, Lille, France, February 17–19, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1770, Springer, Berlin, pp. 395–406, doi:10.1007/3-540-46541-3_33, ISBN   978-3-540-67141-1, MR   1781749
5. Chang, Gerard J.; Kuo, David (1996), "The L(2,1)-labeling problem on graphs", SIAM Journal on Discrete Mathematics , 9 (2): 309–316, CiteSeerX   10.1.1.51.2004 , doi:10.1137/S0895480193245339, MR   1386886
6. Havet, Frédéric; Klazar, Martin; Kratochvíl, Jan; Kratsch, Dieter; Liedloff, Mathieu (2011), "Exact algorithms for L(2,1)-labeling of graphs" (PDF), Algorithmica , 59 (2): 169–194, doi:10.1007/s00453-009-9302-7, MR   2765572, S2CID   2634447
7. Junosza-Szaniawski, Konstanty; Rzążewski, Paweł (2011), "On the complexity of exact algorithm for L(2,1)-labeling of graphs", Information Processing Letters, 111 (14): 697–701, doi:10.1016/j.ipl.2011.04.010, MR   2840535
8. Harary, Frank; Plantholt, Michael (1999), "Graphs whose radio coloring number equals the number of nodes", Graph colouring and applications (Montréal, QC, 1997), CRM Proc. Lecture Notes, vol. 23, Providence, RI: American Mathematical Society, pp. 99–100, MR   1723637