"Записки научных семинаров ПОМИ"

Том 427, стр. 114-124

С.-Петербургский государственный университет, Университетский пр. 28, Петродворец, 198504 Санкт-Петербург, Россия

geraolga91@gmail.com

Аннотация: Пусть $k$ и $g$ -- целые неотрицательные числа. Назовем граф {\it $k$-почти $g$-сферическим}, если его можно изобразить на ориентируемой поверхности рода $g$ так, чтобы каждое ребро пересекало во внутренних точках не более $k$ других ребер. В работе будет доказано, что при $k \leq 4$ для любого $k$-почти $g$-сферического графа на $v$ вершинах количество рёбер не превосходит $(k+3)(v + 2g - 2)$. Также будет доказано, что хроматическое число $k$-почти $g$-сферического графа не превосходит $\frac{2k+7+\sqrt{4k^2+12k+1+16(k+3)g}}2.$ Библ. -- 4 назв.
Ключевые слова: хроматическое число, плоские графы [clique, partition]