О проблеме типа Хивуда для карт с касаниями
Г. В. Ненашев Department of Mathematics, Stockholm University, SE-106 91 Stockholm, Sweden
Аннотация:
В работе рассмотрен класс таких карт на поверхности рода
$g>0$, что в каждой точке сходится не более
$k\geq3$ областей. Мы изучаем хроматические числа таких карт (области должны быть покарашены в разные цвета, если имеют хотя бы одну общую точку) в зависимости от
$g$ и
$k$. Получены верхние оценки на эти хроматические числа в общем случае. В случае
$k=4$ доказана равносильность этой проблемы с нахождением максимального хроматического числа аналогов
$1$-планарных графов на поверхностях и получена более строгая верхняя оценка, нежели в общем случае, а также приведен метод для построение некоторых примеров, подтверждающих точность этой оценки. Помимо этого получена верхняя оценка на максимальное хроматическое число аналога
$2$-планарных графов на поверхности рода
$g>0$. Библ. – 8 назв.
Ключевые слова:
хроматическое число, плоские графы, графы на поверхностях.
УДК:
519.173.2+519.174.7
Поступило: 10.11.2014