L(2,1)-раскраска

L(2,1) раскраска цикла C ₆

L(2,1)-раскраска или L(2,1)-разметка является частным случаем L(h, k)-раскраски . В L(2, 1)-раскраске графа G вершинам G присваиваются цветовые номера таким образом, что соседние вершины получают метки, отличающиеся как минимум на два, а вершины, находящиеся на расстоянии двух друг от друга получают метки, отличающиеся хотя бы на одну.

L(2,1)-раскраска является правильной раскраской , поскольку соседним вершинам присвоены разные цвета. Однако вместо подсчета количества различных цветов, используемых в L(2,1)-раскраске, исследования были сосредоточены на числе L(2,1)-маркировки , наименьшем целом числе $n$ такой, что данный граф имеет L(2,1)-раскраску с использованием номеров цветов от 0 до $n$. Проблема L(2,1)-раскраски была предложена в 1992 году Джеррольдом Григгсом и Роджером Йе на основе схем распределения каналов для радиосвязи. Они доказали, что для циклов, таких как показанный 6-цикл, число L(2,1)-маркировки равно четырем, а для графов степени $\Delta$ это максимум $\Delta ^{2}+2\Delta$.