RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2014 Volume 427, Pages 114–124 (Mi znsl6047)

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

O. E. Samoilova

St. Petersburg State University, St. Petersburg, Russia

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

UDC: 519.173.2+519.174.7

Received: 05.11.2014


 English version:
Journal of Mathematical Sciences (New York), 2016, 212:6, 714–720

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024