Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/10811
Заглавие документа: | Локально ограниченные наследственные подклассы -раскрашиваемых графов |
Авторы: | Зверович, Игорь Эдмундович |
Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
Дата публикации: | 1998 |
Библиографическое описание источника: | Дискретн. анализ и исслед. опер., сер. 1. - 1998. - Т. 5, № 3. - С. 3–16 |
Аннотация: | Правильная $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)$ найдено минимальное множество запрещенных порожденных подграфов. |
URI документа: | http://elib.bsu.by/handle/123456789/10811 |
Располагается в коллекциях: | Архив статей механико-математического факультета до 2016 г. |
Полный текст документа:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
И.Э.Зверович, Локально ограниченные наследственные подклассы -раскрашиваемых графов.pdf | 1,36 MB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.