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

Том 406, стр. 95-106

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

glebnen@mail.ru

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