Laboratory of Mathematical Logic at PDMI

Вторник, 19 ноября, Zoom. Начало в 15:00.

Докладчик: Д.В. Карпов (ПОМИ).

Тема: О изображении на плоскости и правильных раскрасках вершин k-планарных графов.

Abstract

Граф называется k-планарным, если его вершины можно изобразить
на плоскости так, чтобы каждое ребро пересекало не более чем k других.
В докладе будет рассказано об истории вопроса: о классических резуль-
татах Рингеля и Бородина по оценке хроматического числа 1-планарных
графов и связанных с ними вопросах о k-раскрасках планарных графов
(таких раскрасках, в которых все вершины каждой грани размера не бо-
лее k покрашены в разный цвет).
Будет рассказано о вышедшей в 2023 году работе Д.Карпова, в ко-
торой доказано, что вершины 2-планарного графа можно покрасить в 9
цветов, в том числе о том, почему эта задача гораздо труднее аналогич-
ной задачи для 1-планарных графов. А именно, о некоторых вопросах о
каноническом изображении k-планарных графов на плоскости – очевид-
ных для k = 1, содержательных для k = 2 и непонятно, верных ли для
k ≥ 3.
Закончится доклад разговором о том, что можно сделать дальше.

Ключевые слова: 2-планарный граф, плоское изображение графа.