Избранные вопросы теории графов

• Напоминание базовых терминов и обозначений теории графов. Потоки в сетях. Теорема Форда—Фалкерсона. Следствие о существовании целочисленного максимального потока в сети с целочисленными весами. [Diestel, теорема 6.2.2 и следствие 6.2.3]
• Факторизация графов. Теорема Холла (вывод из теоремы о целочисленном потоке). Критерий Кёнига 1-факторизуемости двудольного графа. [Diestel, Следствие 2.1.3] Критерий Петерсена 2-факторизуемости произвольного графа. [Diestel, Следствие 2.1.5] Критерий Татта 1-факторизуемости произвольного графа. [Diestel, теорема 2.2.1] Теорема Анселя о покрытии полного графа двудольными. [Radhakrishnan] Теорема Грэхема—Поллака о разбиении полного графа на полные двудольные. [Aigner]
• Понятия рёберной и вершинной k-связности. [Емеличев, §33] Теорема Менгера (вывод из теоремы о целочисленном потоке). [Свами, раздел 15.7.4] Теорема Мадера. [Diestel, теорема 1.4.3]
• Теорема о шести свойствах двусвязных графов. [Емеличев, теорема 34.1] Лемма о веере. Теорема о циклах в k-связных графах. [Bondy, раздел 9.2] Теоремы о рекурсивном построении двусвязных и трёхсвязных графов. [Diestel, утверждение 3.1.1, теорема 3.2.3] Минимальные связные графы: деревья. Теорема о шести эквивалентных определениях дерева. Деревья блоков и точек сочленения: BC-деревья. [Емеличев, утверждения 34.2—34.6] Метрики на деревьях. [Зарецкий][Зыков, §21]
• Укладки графов. Планарные графы. [Емеличев, §36—37] Миноры и топологические миноры. [Diestel, раздел 1.7] Максимальное число рёбер в планарных графах. [Емеличев, §36—37] Критерии Вагнера и Куратовского. [Скопенков]
• Плоские триангуляции. Трёхсвязность триангуляций. [Емеличев, §38, следствие 39.2] Теорема Татта о границах граней в трёхсвязных планарных графах. Теорема Уитни. [Bondy, теоремы 10.27, 10.28]
• Теорема Вагнера—Фари о прямолинейных укладках планарных графов. Несколько теорем без доказательства о свойствах планарных графов. Минорно-наследственные классы графов, теорема Сеймура—Робертсона (без доказательства). [Diestel, следствие 12.5.2]
• Аналоги теоремы Менгера для квазитриангуляций. Сепараторы в планарных графах. [AlonSeymourThomas]
• Определения хроматического числа, хроматического индекса и списочного хроматического числа. Связь между списочным и обычным хроматическим числом. Простые оценки хроматического числа: оценки через кликовое число, число независимости, количество рёбер. [Diestel, утверждение 5.2.1; Емеличев, следствие 54.2 и др.] Связь списочного хроматического числа и степени вершин. [Alon] Теорема Брукса о хроматическом числе. [Емеличев, стр. 239] Теоремы Визинга и Кёнига о хроматическом индексе. [Diestel, утверждение 5.3.1, теорема 5.3.2]
• Списочное хроматическое число планарных графов: теоремы Войгт и Томассена [Aigner, глава 34].
• Нелокальность хроматического числа. Конструкция Зыкова—Мыцельского: последовательность графов без треугольников с большим хроматическим числом. [Емеличев, теорема 54.5] Теорема Эрдёша о графах со сколь угодно большим обхватом и хроматическим числом. [Diestel, теорема 11.2.2] Следствие о существовании графов с произвольно большим обхватом и связностью. [Diestel, следствие 11.2.3]
• Совершенные графы. Примеры. Теорема Ловаса (слабая гипотеза Бержа о совершенных графах). [Diestel, теорема 5.5.6]
• Экстремальные задачи теории графов. Теорема Турана. Теорема Эрдёша—Стоуна—Симоновица. [Conlon]
• Гамильтоновы циклы. Условия Хватала—Эрдёша. [Diestel, утверждение 10.1.2] Условия Асратяна—Хачатряна. [Diestel, теорема 10.1.3] Гамильтоновы последовательности, условия Хватала. [Diestel, теорема 10.2.1] Гамильтоновы циклы в планарных графах. Теорема Гринбергса. [Емеличев, теорема 44.7]

Материалы

• Слайды лекций
• Интерактивная карта курса

Литература

• В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. М.: Книжный дом «Либроком», 2009.
• К. А. Зарецкий. Построение дерева по набору расстояний между висячими вершинами // УМН, 1965, том 20, выпуск 6(126), стр. 90–92
• А. А. Зыков. Теория конечных графов. Новосибирск: Наука, 1969.
• М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. М.: Мир, 1984.
• А. Б. Скопенков. Вокруг критерия Куратовского планарности графов // Математическое просвещение, 2005, выпуск 9, стр. 116—128
• M. Aigner, G. M. Ziegler. Proofs From THE BOOK. Fourth Edition. Springer, 2009.
• N. Alon. Degrees and choice numbers // Random Structures and Algorithms, 16(2000), 364-368.
• N. Alon, P. D. Seymour and R. Thomas. Planar separators, SIAM J. Discrete Math. 7 (1994), 184-193.
• B. Bollobás. Modern Graph Theory. Springer, 1998.
• J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, 2008.
• D. Conlon. Extremal Graph Theory Course. Lecture notes.
• R. Diestel. Graph Theory. Fourth Edition. Springer-Verlag, 2010.
• J. Radhakrishnan. Entropy and Counting // IIT Kharagpur, Golden Jubilee Volume on Computational Mathematics, Modelling and Algorithms. New Delhi, 2001.