RUS  ENG
Полная версия
ЖУРНАЛЫ // Записки научных семинаров ПОМИ // Архив

Зап. научн. сем. ПОМИ, 2014, том 427, страницы 114–124 (Mi znsl6047)

О графах, которые можно изобразить на ориентируемых поверхностях с малым числом пересечений на ребре

О. Е. Самойлова

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

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

Ключевые слова: хроматическое число, плоские графы, графы на поверхностях.

УДК: 519.173.2+519.174.7

Поступило: 05.11.2014


 Англоязычная версия: Journal of Mathematical Sciences (New York), 2016, 212:6, 714–720

Реферативные базы данных:


© МИАН, 2024