Радиораскраска в планарных графах: различия между версиями

'''Определение 3.''' Пусть дан граф G(V, E). <math>G^2 \;</math> представляет собой граф с тем же множеством вершин V и множеством ребер <math>E': \{ u, v \} \in E' \;</math> в том и только том случае, если <math>d(u, v) \le 2 \;</math> в G.

Родственная задача заключается в раскраске квадрата графа G, <math>G^2 \;</math>, таким образом, чтобы никакие две соседние вершины в G2 не были раскрашены в один цвет. Целью является использование минимального числа цветов, которое обозначается <math>\chi (G^2) \;</math> и называется [[хроматическое число|хроматическим числом]] квадрата графа G. В [5, 6] было впервые замечено, что для любого графа G значение <math>X_{order}(G) \;</math> совпадает с (вершинным) хроматическим числом <math>G^2 \;</math>, т.<math>е. X_{order}(G) = \chi (G^2) \;</math>.