|
Записки научных семинаров ПОМИ, 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 назв.
Ключевые слова:
хроматическое число, плоские графы, графы на поверхностях.
Поступило: 05.11.2014
Образец цитирования:
О. Е. Самойлова, “О графах, которые можно изобразить на ориентируемых поверхностях с малым числом пересечений на ребре”, Комбинаторика и теория графов. VII, Зап. научн. сем. ПОМИ, 427, ПОМИ, СПб., 2014, 114–124; J. Math. Sci. (N. Y.), 212:6 (2016), 714–720
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl6047 https://www.mathnet.ru/rus/znsl/v427/p114
|
|