On a Heawood-Type Problem for Maps with Tangencies
- Authors: Nenashev G.V.1
-
Affiliations:
- Stockholm University
- Issue: Vol 212, No 6 (2016)
- Pages: 688-697
- Section: Article
- URL: https://journals.rcsi.science/1072-3374/article/view/237127
- DOI: https://doi.org/10.1007/s10958-016-2699-z
- ID: 237127
Cite item
Abstract
The class of maps on a surface of genus g > 0 such that each point belongs to at most k ≥ 3 regions is studied. The problem is to estimate in terms of g and k the chromatic number of such a map (it is assumed that the regions having a common point must have distinct colors). In general case, an upper bound of the chromatic number is established. For k = 4, it is proved that the problem is equivalent to finding the maximal chromatic number for analogs of 1-planar graphs on a surface of genus g. In this case, a more strong bound is obtained and a method of constructing examples, for which this bound is achieved, is presented. In addition, for analogs of 2-planar graphs on a surface of genus g, an upper bound on maximal chromatic number is proved.
About the authors
G. V. Nenashev
Stockholm University
Author for correspondence.
Email: glebnen@mail.ru
Sweden, Stockholm