Локально ограниченные наследственные подклассы $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.