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

Родственная задача заключается в раскраске квадрата графа G, <math>G^2 \;</math>, таким образом, чтобы никакие две соседние вершины в <math>G^2 \;</math> не были раскрашены в один цвет. Целью является использование минимального числа цветов, которое обозначается <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>.