Logo BSU

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ: http://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-раскраски графов.pdf1,1 MBAdobe PDFОткрыть


Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.