|
Zapiski Nauchnykh Seminarov 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$.
Received: 05.11.2014
Citation:
O. E. Samoilova, “On graphs which can be drawn on an orientable surface with small number of intersections on an edge”, Combinatorics and graph theory. Part VII, Zap. Nauchn. Sem. POMI, 427, POMI, St. Petersburg, 2014, 114–124; J. Math. Sci. (N. Y.), 212:6 (2016), 714–720
Linking options:
https://www.mathnet.ru/eng/znsl6047 https://www.mathnet.ru/eng/znsl/v427/p114
|
Statistics & downloads: |
Abstract page: | 104 | Full-text PDF : | 25 | References: | 29 |
|