Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dfc/2012/Program2/bogdanov-summary.pdf Дата изменения: Tue Oct 16 10:33:12 2012 Дата индексирования: Mon Feb 4 18:25:58 2013 Кодировка: Windows-1251

Графы с малым локальным хроматическим числом

Краткое изложение заявки
И. И. Богданов

Данный проект посвящ?н экстремальной теории графовF Целью его является изучение связи локальных и глобальных свойств раскрасок графовF Важность этих вопросов и интерес к ним в последние годы повышаетсяD в частностиD в связи с исследованиями особо больших графов " напримерD связанных с компьютерными сетямиF Нас в первую очередь интересует вопрос о связи между хроматическим числом графа и его rEлокальным хроматическим числомD то есть максимальным хроматическим числом его @индуцированногоA подграфа радиуса rF Известный результат Эрд?ша о графах с большим хроматическим числом без малых циклов показываетD что ограниченность локального хромаE тического числа сама по себе не влеч?т никаких ограничений на глобальное хроматическое числоF Однако все известные подобные примеры @конструктивные или неконструктивныеA доE статочно великиF Мы исследуем связь между данными двумя числами при дополнительных ограниченияхD в первую очередь " на количество вершинF Известный результат КирстедаD Семереди и ТроттеE ра да?т оценку на хроматическое число графа в терминах количества вершин и rEлокального хроматического числаF Однако этот результат работает лишь при количестве вершинD не слишE ком большом по сравнению с радиусом rF Известны также явные подобные оценки в случаяхD когда глобальное хроматическое число или радиус малыF Недавно автором совместно с СF ЛF Берловым были получены нетривиальные нижние оценE ки на количество вершин графа с произвольным хроматическим числомD не содержащим маE лых неч?тных циклов @иначе говоряD с rEлокальным хроматическим числом PAY при этом важE ную роль играет оценка максимального количества вершин в rEокрестности вершины графаF В проекте предполагается обобщить этот результат на произвольные графы с ограниченным rEхроматическим числомF Методы из предыдущей статьиD по видимостиD допускают усилениеD которое само по себе позволит получить оценку на количество вершин порядка Cr r+1 @здесь " хроматическое число графаAF Однако прямолинейное применение этих методовD поEвидимомуD даст весьма неточные оценE ки на количество вершин при малых nY соответственноD и @рекуррентныеA оценки на б? ольшие значения будут ощутимо неточныF Для их улучшения требуется оценить размер наибольшей окрестности вершины радиуса rF При малых значениях радиуса с этой целью можно испольE зовать известные результатыY для ?переходных? же значенийD когда радиус и хроматическое число имеют одинаковый порядокD для подобной оценки требуются новые методыF Эти методы также планируется разработатьF Кроме тогоD мы собираемся получить более точные оценки при зафиксированном малом значении одного из параметров или rF НаконецD отметим ещ? один вопросD тесно связанный с этой тематикойF Одной из важE ных проблем в изучении nEкритических графов @то есть минимальных по включению nE хроматических графовA является оценка минимального количества р?бер в nEкритическом @иD как следствиеD в nEхроматическомA графеF ЗаметимD что оценка размера ограниченной окрестE ности UG (r, v ) влеч?т за собой оценку числа р?бер в этой окрестностиF Эта оценка может быть усилена в том случаеD если хроматическое число этой окрестности не слишком малоF Таким обE разомD представляетсяD что планируемые результаты " вкупе с соображениямиD связанными с хроматическим числом окрестностиD " позволят оценить число р?бер критического графа как минимум в случае малого локального хроматического числа этого графаF Последнее условиеD возможноD удастся опуститьF