Laboratory of Mathematical Logic at PDMI

Пятница, 21 мая, комната 106. Начало в 17:00.

Докладчик: В. Васильченко.

Тема: Оценки на количество ребер в почти планарном графе.

Abstract

В докладе рассматривается вопорс о максимальном числе рёбер в графе, который можно изобразить на плоскости так, чтобы каждое ребро пересекало во внутренних точках не более k других ребер (мы будем называть такие графы k-почти планарными). Как известно, для планарного графа на v вершинах (то есть графа, который можно изобразить на плоскости без пересечений рёбер) без петель и кратных рёбер максимальное количество рёбер равно 3v-6, где v -- это количество вершин. Оказывается, что если разрешить рёбрам иметь не более одного пересечения (почти планарный граф), то это количество увеличится до 4v-8. Если же разрешить рёбрам иметь не более двух пересечений (2-почти планарный граф), то искомое количество будет порядка 5v, а точнее: если v сравнимо с 0 или 1 по модулю 3, то ответ 5v-11; если v сравнимо с 2 по модулю 3, то ответ 5v-10.