On Heawood-type problem for maps with tangencies

G. V. Nenashev

Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VII, Tome 427 (2014), pp. 74-88

Résumé

The class of maps on a surface of genus $g>0$ such that each point belongs to at most $k\geq3$ regions is studied. We study chromatic numbers of such maps (regions having a common point must have distinct colors) in dependence on $g$ and $k$. In general case, upper bounds on these chromatic numbers are proved. In case $k=4$, it is proved that the problem described above is equivalent to the problem of finding the maximal chromatic number for analogues of $1$-planar graphs on a surface of genus $g$. In this case a more strong bound than in general case is obtained and a method of constructing examples which confirm accuracy of our bound is presented. An upper bound on maximal chromatic number for analogues of $2$-planar graphs on a surface of genus $g$ is proved.