On Graphs, Which Can be Drawn on an Orientable Surface with Small Number of Intersections on an Edge

Аннотация

Let k and g be nonnegative integers. A graph is said to be k-nearly g-spherical if it can be drawn on an orientable surface of genus g so that each edge intersects at most k other edges in interior points. It is proved that if k ≤ 4, then the edge number of a k-nearly g-spherical graph on v vertices does not exceed (k + 3)(v + 2g − 2). It is also shown that the chromatic number of a k-nearly g-spherical graph does not exceed\( \frac{2k+7+\sqrt{4{k}^2+12k+1+16\left(k+3\right)g}}{2} \). Bibliography: 4 titles.