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

Зап. научн. сем. ПОМИ, 2012, том 406, страницы 95–106 (Mi znsl5291)

Эта публикация цитируется в 2 статьях

Оценка хроматического числа почти планарного графа

Г. В. Ненашев

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

Аннотация: В работе доказано, что если граф может быть нарисован на плоскости так, чтобы каждое ребро пересекало не более одного другого, то хроматическое число такого графа не превосходит 7. Также получена оценка $\chi(G)\leq\frac{9+\sqrt{17+64g}}2$ для графа $G$, который может быть нарисован на поверхности рода $g$ так, чтобы каждое ребро пересекало не более одного другого. Библ. – 8 назв.

Ключевые слова: хроматическое число.

УДК: 519.173.2+519.174.7

Поступило: 03.11.2012


 Англоязычная версия: Journal of Mathematical Sciences (New York), 2014, 196:6, 784–790

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


© МИАН, 2024