On graphs which can be drawn on an orientable surface with small number of intersections on an edge

O. E. Samoilova

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

Résumé

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$.