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

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

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

Эта статья, связанная с теорией графов, является заглушкой . Вы можете помочь Википедии, расширив ее.

• в
• т
• е