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

Перейти к навигации Перейти к поиску
Строка 47: Строка 47:




Еще одна родственная задача заключается в раскраске квадрата графа G, G2, таким образом, чтобы никакие две соседние вершины в G2 не были раскрашены в один цвет. Целью является использование минимального числа цветов, которое обозначается /(G2) и называется хроматическим числом квадрата графа G. В [5, 6] было впервые замечено, что для любого графа G значение Xorder(G) совпадает с (вершинным) хроматическим числом G2, т.е. Xorder(G) = 2.
Родственная задача заключается в раскраске квадрата графа 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>.


== Основные результаты ==
== Основные результаты ==
4551

правка

Навигация