"Записки научных семинаров ПОМИ"
Том 427, стр. 74-88
О проблеме типа Хивуда для карт с касаниями
Г. В. Ненашев
Department of Mathematics,
Stockholm University,
SE - 106 91 Stockholm, Sweden
glebnen@mail.ru
- Аннотация:
В работе рассмотрен класс таких карт на поверхности рода $g>0$, что в
каждой точке сходится не более $k\geq 3$ областей.
Мы изучаем хроматические числа таких карт (области должны быть покарашены
в разные цвета, если имеют хотя бы одну общую точку) в зависимости от $g$
и $k$.
Получены верхние оценки на эти хроматические числа в общем случае. В
случае $k=4$ доказана равносильность этой проблемы с нахождением
максимального хроматического числа аналогов $1$-планарных графов на
поверхностях и получена более строгая верхняя оценка, нежели в общем
случае, а также приведен метод для построение некоторых примеров,
подтверждающих точность этой оценки. Помимо этого получена верхняя оценка
на максимальное хроматическое число аналога $2$-планарных графов на
поверхности рода $g>0$.
Библ. -- 8 назв.
- Ключевые слова: хроматическое число, плоские графы
[graph embedding, map, surface, chromatic number, 1-planar
graph, topological graph]
Полный текст(.pdf)