Локально ограниченные наследственные подклассы -раскрашиваемых графов

Abstract

Правильная $k$-раскраска $\mathfrak{C}_1,\mathfrak{C}_2,\dots,\mathfrak{C}_k$ множества вершин графа $G$ называется $l$-ограниченной $(l\geqslant 0)$, если $\vert\mathfrak{C}_1\setminus N(u)\vert\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)$ найдено минимальное множество запрещенных порожденных подграфов.