On Property M(4) of the Graph Kn 2 + Om

Abstract

Given a list L(v) for each vertex v, we say that the graph G is L-colorable if there is a proper vertex coloring of G where each vertex v takes its color from L(v). The graph is uniquely k-list colorable if there is a list assignment L such that jL(v)j = k for every vertex v and the graph has exactly one L-coloring with these lists. If a graph G is not uniquely k-list colorable, we also say that G has property M(k). The least integer k such that G has the property M(k) is called the m-number of G, denoted by m(G). In this paper, we characterize uniquely list colorability of the graph G = Kn 2 +Or. We shall prove that m(K2 2 + Or) = 4 if and only if r > 9, m(K3 2 + Or) = 4 for every 1 6 r 6 5 and m(K4 2 + O1) = 4

Учитывая список 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