4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 47: | Строка 47: | ||
Родственная задача заключается в раскраске квадрата графа 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>. | |||
== Основные результаты == | == Основные результаты == |
правка