Laboratory of Mathematical Logic at PDMI

Пятница, 30 мая, ауд. 203. Начало в 15:00.

Докладчик: Глеб Ненашев (СПбГУ).

Тема: Об проблеме Хивуда для карт с касаниями.

Abstract

Задачи о том, как связаны между собой возможность нарисовать граф на различных типах поверхностей без пересечения ребер и хроматические характеристики графа, являются одними из самых старых в теории графов. Самая известная задача подобного рода --- проблема четырех красок. В общей постановке задачи основные результаты --- это найденная П. ДЖ. Хивудом верхняя оценка хроматического числа графа, который можно изобразить без пересечений на поверхности рода (), и точные примеры построенные Рингелем и Янгсом.

Как всем известно изначальная формулировка проблемы 4-х красок была про покраску стран на карте, а формулировка с графом это всего переформулировка для графов. Теперь вспомним изначальную проблему Хивуда в терминах карт и стран: дана поверхность рода разбитая на области, и мы красим так чтобы не было двух областей одного цвета имеющих общую границу. Эта формулировка эквивалентна тому, что поверхность рода разбита на области так, что в каждой точке сходятся максимум 3 области, и мы красим так чтобы все касающиеся области были разного цвета. Мы обобщим этот результат на случай, когда в каждой точке сходятся не более областей. А так же в случае k=4,5 поговорим о формулировках в терминах графов связанные с обобщением почти планарных графов.И в случае k=4 будет построен точный пример для поверхности с большим родом и будет рассказана идея построения почти точных примеров.