Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/10808
Заглавие документа: | Сильные k-раскраски графов |
Авторы: | Зверович, Игорь Эдмундович |
Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
Дата публикации: | 2001 |
Библиографическое описание источника: | Дискрет. матем. - 2001. - Т.13, № 1. - С. 78–89 |
Аннотация: | Правильная $k$-раскраска $C_1,\ldots,C_k$ графа $G$ называется сильной, если для любой вершины $u\in VG$ существует индекс $i\in\{1,\ldots,k\}$ такой, что $u$ смежна с каждой вершиной класса $C_i$. В этой работе рассмотрен класс $S(k)$ сильно $k$-раскрашиваемых графов и показано, что задача распознавания $S(k)$ является NP-полной при любом $k\ge4$, а при $k=3$ — полиномиально разрешимой. Мы даем характеризацию класса $S(3)$ в терминах запрещенных порожденных подграфов и решаем проблему единственности сильной 3-раскраски. |
URI документа: | http://elib.bsu.by/handle/123456789/10808 |
Располагается в коллекциях: | Архив статей механико-математического факультета до 2016 г. |
Полный текст документа:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
И.Э.Зверович, Сильные k-раскраски графов.pdf | 1,1 MB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.