Материал конференции: "XIV международный научный семинар "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (20-25 июня 2022 г., Москва)"
Авторы:Карпов Д.В.
Об изображениях на плоскости и раскрасках k-планарных графов
Аннотация:
Граф называется k-планарным, если его можно так изобразить на плоскости, что каждое ребро пересекает не более чем k других. Наверное, впервые появилось такое обобщение в работе Рингеля в 1965 году - там были рассмотрены 1-планарные графы и доказано, что любой такой граф имеет правильную раскраску вершин в 7 цветов. Позже были определены k-планарные графы для всех натуральных k, исследовались вопросы об оценке на количество ребер в таких графах, оценке хроматического числа, различные вопросы об их изображениях на плоскости. В докладе будет рассказано о классических и современных результатах из этой области.
