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

Zap. Nauchn. Sem. POMI, 2012 Volume 406, Pages 95–106 (Mi znsl5291)

This article is cited in 2 papers

On a bound on the chromatic number of almost planar graph

G. V. Nenashev

Saint-Petersburg State University, Saint-Petersburg, Russia

Abstract: Let $G$ be a graph, which can be drawn on the plane such that any edge intersects at most one other edge. We prove, that the chromatic number of $G$ does not exceed 7. We also prove the bound $\chi(G)\leq\frac{9+\sqrt{17+64g}}2$ for a graph $G$, which can be drawn on the surface of genus $g$, such that any edge intersects at most one other edge.

Key words and phrases: topological graphs, planar graphs.

UDC: 519.173.2+519.174.7

Received: 03.11.2012


 English version:
Journal of Mathematical Sciences (New York), 2014, 196:6, 784–790

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025