|
Записки научных семинаров ПОМИ, 2012, том 406, страницы 95–106
(Mi znsl5291)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Оценка хроматического числа почти планарного графа
Г. В. Ненашев С.-Петербургский государственный университет, Санкт-Петербург, Россия
Аннотация:
В работе доказано, что если граф может быть нарисован на плоскости так, чтобы каждое ребро пересекало не более одного другого, то хроматическое число такого графа не превосходит 7. Также получена оценка $\chi(G)\leq\frac{9+\sqrt{17+64g}}2$ для графа $G$, который может быть нарисован на поверхности рода $g$ так, чтобы каждое ребро пересекало не более одного другого. Библ. – 8 назв.
Ключевые слова:
хроматическое число.
Поступило: 03.11.2012
Образец цитирования:
Г. В. Ненашев, “Оценка хроматического числа почти планарного графа”, Комбинаторика и теория графов. V, Зап. научн. сем. ПОМИ, 406, ПОМИ, СПб., 2012, 95–106; J. Math. Sci. (N. Y.), 196:6 (2014), 784–790
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl5291 https://www.mathnet.ru/rus/znsl/v406/p95
|
Статистика просмотров: |
Страница аннотации: | 209 | PDF полного текста: | 71 | Список литературы: | 42 |
|