Geodesic
On graphs which can be drawn on an orientable surface with small number of intersections on an edge
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VII, Tome 427 (2014), pp. 114-124 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Let $k$ and $g$ be nonnegative integers. We call a graph $k$-nearly $g$-spherical, if it can be drawn on an orientable surface of genus $g$ such that each edge intersects at most $k$ other edges in inner points. It is proved that for $k\leq4$ the number of edges of a $k$-nearly $g$-spherical graph on $v$ vertices does not exceed $(k+3)(v+2g-2)$. It is also proved that the chromatic number of a $k$-nearly $g$-spherical graph does not exceed $\frac{2k+7+\sqrt{4k^2+12k+1+16(k+3)g}}2$. 
@article{ZNSL_2014_427_a7,
     author = {O. E. Samoilova},
     title = {On graphs which can be drawn on an orientable surface with small number of intersections on an edge},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {114--124},
     year = {2014},
     volume = {427},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2014_427_a7/}
}
TY  - JOUR
AU  - O. E. Samoilova
TI  - On graphs which can be drawn on an orientable surface with small number of intersections on an edge
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2014
SP  - 114
EP  - 124
VL  - 427
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2014_427_a7/
LA  - ru
ID  - ZNSL_2014_427_a7
ER  - 
%0 Journal Article
%A O. E. Samoilova
%T On graphs which can be drawn on an orientable surface with small number of intersections on an edge
%J Zapiski Nauchnykh Seminarov POMI
%D 2014
%P 114-124
%V 427
%U http://geodesic.mathdoc.fr/item/ZNSL_2014_427_a7/
%G ru
%F ZNSL_2014_427_a7
O. E. Samoilova. On graphs which can be drawn on an orientable surface with small number of intersections on an edge. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VII, Tome 427 (2014), pp. 114-124. http://geodesic.mathdoc.fr/item/ZNSL_2014_427_a7/

[1] J. Pach, G. Toth., “Graphs drawn with few crossing per edge”, Combinatorica, 17:3 (1997), 427–439 | DOI | MR | Zbl

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

[3] D. V. Karpov, “Verkhnyaya otsenka kolichestva reber v dvudolnom pochti planaronom grafe”, Zap. nauchn. semin. POMI, 406, 2012, 12–30 | MR

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