Geodesic
On Heawood-type problem for maps with tangencies
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VII, Tome 427 (2014), pp. 74-88 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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. 
@article{ZNSL_2014_427_a4,
     author = {G. V. Nenashev},
     title = {On {Heawood-type} problem for maps with tangencies},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {74--88},
     year = {2014},
     volume = {427},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2014_427_a4/}
}
TY  - JOUR
AU  - G. V. Nenashev
TI  - On Heawood-type problem for maps with tangencies
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2014
SP  - 74
EP  - 88
VL  - 427
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2014_427_a4/
LA  - ru
ID  - ZNSL_2014_427_a4
ER  - 
%0 Journal Article
%A G. V. Nenashev
%T On Heawood-type problem for maps with tangencies
%J Zapiski Nauchnykh Seminarov POMI
%D 2014
%P 74-88
%V 427
%U http://geodesic.mathdoc.fr/item/ZNSL_2014_427_a4/
%G ru
%F ZNSL_2014_427_a4
G. V. Nenashev. On Heawood-type problem for maps with tangencies. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VII, Tome 427 (2014), pp. 74-88. http://geodesic.mathdoc.fr/item/ZNSL_2014_427_a4/

[1] K. Appel, W. Haken, Every Planar Map Is Four Colorable, Contemp. Math., 98, A.M.S., 1989 | DOI | MR | Zbl

[2] K. Appel, W. Haken, “Every map is four colourable, Part I: Discharging”, Illinois Journal of Mathematics, 21 (1977), 429–490 | MR | Zbl

[3] K. Appel, W. Haken, “Every map is four colourable, Part II: Reducibility”, Illinois Journal of Mathematics, 21 (1977), 491–567 | MR | Zbl

[4] O. V. Borodin, “Solution of Ringel's problems on vertex-face coloring of plane graphs and coloring of 1-planar graphs”, Met. Diskret. Anal., 41 (1984), 12–26 | MR | Zbl

[5] P. J. Heawood, “Map colour theorem”, Quart. J. Math., 24 (1890), 332–338 | Zbl

[6] G. V. Nenashev, “Otsenka khromaticheskogo chisla pochti planarnogo grafa”, Zap. nauchn. semin. POMI, 406, 2012, 95–106 | MR

[7] G. Ringel, J. W. T. Youngs, “Solution of the Heawood map-coloring problem”, Proc. Nat. Acad. Sci. USA, 60:2 (1968), 438–445 | DOI | MR | Zbl

[8] N. Robertson, D. Sanders, P. Seymour, R. Thomas, “The Four-Colour Theorem”, J. Comb.Theory, Series B, 70 (1997), 2–44 | DOI | MR | Zbl