"Записки научных семинаров ПОМИ"

Том 391, стр. 35-44

Физико-математический лицей No. 239, ул. Кирочная в. 8а., Санкт-Петербург 191028, Россия

sberlov@rambler.ru

Московский физико-технический институт (государственный университет), Институтский пер., 9, г. Долгопрудный, Московская обл. 141700, Россия

ilya.i.bogdanov@gmail.com

Аннотация: В работе приводятся нижние оценки количества вершин в графе с большим хроматическим числом, не содержащем маленьких нечётных циклов. Библ. -- 6 назв.
Ключевые слова: хроматическое число, нечетные циклы, обхват [chromatic number, odd cycles, girth]