Том 5, серия 1, номер 3, 1998 г., Стр. 3-16

УДК 519.17
И. Э. Зверович
Локально ограниченные наследственные подклассы $k$-раскрашиваемых графов

Аннотация:
Правильная $k$-раскраска $\mathfrak C_1,\mathfrak C_2,\dots,\mathfrak C_k$ множества вершин графа $G$ называется $l$-ограниченной $(l\geqslant 0)$, если $|\mathfrak C_1\setminus N(u)|\leqslant l$ для любого $i=1,2,\dots,k$ и любой вершины $u\in VG\setminus \mathfrak C_i$, где $N(U)$ – окружение вершины $u$. Пусть $C(k,l)$ есть класс всех графов, имеющих $l$-ограниченную $k$-раскраску ($k\geqslant 1$ и $l\geqslant 0$). Показано, что каждый класс $C(k,l)$ имеет конечную характеризацию в терминах запрещенных порожденных подграфов. Этот результат влечет существование полиномиальных алгоритмов распознавания $C(k,l)$. Для класса $C(3,1)$ найдено минимальное множество запрещенных порожденных подграфов.
Ил. б, библиогр. 2.

Зверович И. Э. ¹
1. Белорусский государственный университет,
пр. Фр. Скорины, 4, 220050 Минск, Беларусь
е-mail: igor@mmf.bsu.unibel.by

Статья поступила 2 декабря 1997 г.