Сибирский федеральный университет

Учитывая список L(v) для каждой вершины v, мы говорим, что граф G является L-раскрашиваемым, если существует правильная раскраска вершин графа G, при которой каждая вершина v принимает свой цвет из L(v). Граф однозначно раскрашивается в k-список, если существует такое задание списка L, что jL(v)j = k для каждой вершины v и граф имеет ровно одну L-раскраску этими списками. Если граф G не является однозначно раскрашиваемым в k-списке, мы также говорим, что G обладает свойством M(k). Наименьшее целое число k такое, что G обладает свойством M(k), называется m-числом G и обозначается m(G). В этой статье мы однозначно характеризуем список раскрашиваемости графа G = Kn 2 + Or. Мы докажем, что m(K2 2 + Or) = 4 тогда и только тогда, когда r > 9, m(K3 2 + Or) = 4 для каждого 1 6 r 6 5 и m(K4 2 + O1) = 4