"Записки научных семинаров ПОМИ"
Том 417, стр. 5-10
Антиклики и хроматические числа в круговых графах
С. Л. Берлов
Физико-математический лицей No. 239,
ул. Кирочная д. 8а., 191028 С.-Петербург;
Ярославский Государственный унивеситет,
Лаборатория дискретной и вычислительной
геометрии им. Делоне, ул. Советская, д.14
150000 Ярославль, Россия
sberlov@rambler.ru
- Аннотация: Пусть вершины кругового графа разбиты на несколько групп.
Получены нижние оценки на размер независимого множества, содержащегося в одной из
групп разбиения.
Библ. -- 7 назв.
- Ключевые слова: граф, хроматическое число, антиклика,
круговой граф
[circle graph, chromatic number, clique, independent set]
Полный текст(.pdf)