On a Heawood-Type Problem for Maps with Tangencies

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.