Аннотация:
Граф называется $k$-планарным, если его можно так изобразить на плоскости, что каждое ребро пересекает не более чем $k$ других.
Наверное, впервые появилось такое обобщение планарных графов в работе Рингеля в 1965 году — там были рассмотрены 1-планарные графы и доказано,
что любой такой граф имеет правильную раскраску вершин в 7 цветов.
Позже были определены $k$-планарные графы для всех натуральных $k$. В работах Рингеля, Паха, Тота, Оре, Бородина и других исследовались вопросы об оценке на количество ребер в таких графах,
оценке хроматического числа, различные вопросы об их изображениях на плоскости.
В докладе будет рассказано о классических и современных результатах из этой области.
|
