Home

Пятница 11 мая, 18-00, ауд. 106

Пятница, 11 мая, ауд. 106. Начало в 18:00.

Докладчик: Глеб Ненашев (СПбГУ).

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

Abstract

Граф называется k-почти планарным, если его можно изобразить на плоскости так чтобы каждое ребро пересекало не более $k$ других. Будет доказано, что для 3-почти планарного графа $G$ верна оценка $e(G)\leq 5.5v(G) - 11$. А так же показана серия примеров, когда $e(G)= 5.5v(G) - 15$.