|
Дискретный анализ и исследование операций, сер. 1, 1998, том 5, выпуск 3, страницы 3–16
(Mi da358)
|
|
|
|
Локально ограниченные наследственные подклассы $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.
Статья поступила: 02.12.1997
Образец цитирования:
И. Э. Зверович, “Локально ограниченные наследственные подклассы $k$-раскрашиваемых графов”, Дискретн. анализ и исслед. опер., сер. 1, 5:3 (1998), 3–16
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da358 https://www.mathnet.ru/rus/da/v5/s1/i3/p3
|
Статистика просмотров: |
Страница аннотации: | 143 | PDF полного текста: | 59 |
|