Радиоокраска

Поиск радиоокраски с заданной шириной является NP-полной задачей, даже если рассматривать только плоские графы, сплит-графы или дополнения бипартитных графов^[4]. Задача также является NP-трудной для хордальных графов и остаётся NP-полной для двудольных планарных графов с максимальной степенью 3^[5]. Однако для деревьев и кографов задача решается за полиномиальное время^[6]. Существует полиномиальный алгоритм сложности ${\displaystyle O(n^{4})}$ для чётных циклов и некоторых циркулянтных графов^[7]. Для произвольных графов задача решается за экспоненциальное время, значительно быстрее, чем полный перебор всех возможных раскрасок^[8][9]. В рамках параметризованной сложности разработан FPT-алгоритм для графов с ограниченной древесной шириной^[10]. В общем случае для произвольных графов задача трудно поддаётся аппроксимации с константным коэффициентом, однако полиномиальные алгоритмы с доказанной гарантией существуют для единичных дисковых графов^[11].

Хотя номер радиоокраски n-вершинного графа может изменяться от 1 до 2n - 1, почти все графы на n вершинах имеют номер радиоокраски ровно n. Это связано с тем, что такие графы почти всегда имеют диаметр не менее двух (что требует разных «цветов» для всех вершин, и, соответственно, номер радиоокраски не меньше n), а также почти всегда содержат гамильтонов путь в дополнении графа. Соседним вершинам этого пути можно присвоить последовательные метки, что позволяет выполнить радиоокраску без пропуска номеров^[12].

Для декартова произведения дерева и полного графа установлена нижняя граница радиочисла, а также определены необходимые и достаточные условия для её достижения. Кроме того, найдены точные значения радиочисла для некоторых конкретных классов таких графов^[13]..

В рамках исследования радио-средней разметки (англ. Radio Mean Labeling) доказано, что для коллекции всех гусеничных деревьев (T_{n,d}) выполняется неравенство n ≤ rmn(T_{n,d}) ≤ rmn(P_n), причём каждое целое число в этом диапазоне является радио-средним числом некоторого гусеничного дерева из данной коллекции.

В задаче назначения каналов (Channel Assignment Problem) ограничения на радиопомехи моделируются с помощью теории графов: чем ближе расположены передатчики, тем больше должна быть разница между назначенными им частотами. Эти физические ограничения транслируются в математические условия на расстояние между вершинами через различные модели разметки и раскраски:^[14][15]

• L-разметка (например, ${\displaystyle (p,q)}$-раскраска): разность между номерами каналов, назначенных вершинам, должна быть не меньше заданного значения, зависящего от расстояния между ними. Например, для смежных вершин разница составляет как минимум ${\displaystyle p}$, а для вершин на расстоянии 2 — как минимум ${\displaystyle q}$^[16].^[17]
• Раскраска на расстоянии ${\displaystyle d}$ (distance-${\displaystyle d}$ coloring): любые вершины, находящиеся на расстоянии не более ${\displaystyle d}$, должны получать строго разные цвета (каналы) во избежание конфликтов^[18].

Ещё одной вариацией является радио-геометрическая средняя разметка (англ. radio geometric mean labeling). Для связного графа ${\displaystyle G}$ это инъективная функция ${\displaystyle f}$ из множества вершин в множество натуральных чисел, удовлетворяющая условию ${\displaystyle d(u,v)+\lceil {\sqrt {f(u)\cdot f(v)}}\rceil \geq 1+diam(G)}$ для любых двух различных вершин ${\displaystyle u}$ и ${\displaystyle v}$, где ${\displaystyle d(u,v)}$ — расстояние между ними, а ${\displaystyle diam(G)}$ — диаметр графа^[19]. Помимо эффективного распределения радиоканалов, эта разметка применяется в криптографии: её комбинация с вычислением эксцентриситета вершин и традиционными криптосистемами (такими как RSA или аффинный шифр) обеспечивает дополнительный уровень защиты сообщений в публичных каналах связи^[20].