Вторник 19.11. Д.В. Карпов (ПОМИ): "О изображении на плоскости и правильных раскрасках вершин k-планарных графов"
PDMI seminars
Тема: О изображении на плоскости и правильных раскрасках вершин k-планарных графов
Место: Zoom
Время: 19.11.2024, 15:00
Докладчик: Д.В. Карпов (ПОМИ)
Abstract:
Граф называется k-планарным, если его вершины можно изобразить
на плоскости так, чтобы каждое ребро пересекало не более чем k других.
В докладе будет рассказано об истории вопроса: о классических резуль-
татах Рингеля и Бородина по оценке хроматического числа 1-планарных
графов и связанных с ними вопросах о k-раскрасках планарных графов
(таких раскрасках, в которых все вершины каждой грани размера не бо-
лее k покрашены в разный цвет).
Будет рассказано о вышедшей в 2023 году работе Д.Карпова, в ко-
торой доказано, что вершины 2-планарного графа можно покрасить в 9
цветов, в том числе о том, почему эта задача гораздо труднее аналогич-
ной задачи для 1-планарных графов. А именно, о некоторых вопросах о
каноническом изображении k-планарных графов на плоскости – очевид-
ных для k = 1, содержательных для k = 2 и непонятно, верных ли для
k ≥ 3.
Закончится доклад разговором о том, что можно сделать дальше.
Ключевые слова: 2-планарный граф, плоское изображение графа.