"Записки научных семинаров ПОМИ"
Том 391, стр. 149-156
Оценка хроматического числа графа пересечения хорд на окружности без $K_4$
Г. В. Ненашев
С.-Петербургский
государственный университет,
Университетский пр. 28,
Петродворец, 198504 Санкт-Петербург, Россия
glebnen@mail.ru
- Аннотация:
Пусть $G$ -- граф пересечения хорд на окружности,
не содержащий клики на четырех вершинах. В работе
доказано, что хорды данного графа можно покрасить
правильным образом в 30 цветов.
Библ. -- 7 назв.
- Ключевые слова:граф пересечения хорд, правильная раскраска, хроматическое число
[circle graph, proper coloring, chromatic number]
Полный текст(.pdf)