|
Zapiski Nauchnykh Seminarov POMI, 2012, Volume 406, Pages 95–106
(Mi znsl5291)
|
|
|
|
This article is cited in 2 scientific papers (total 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.
Received: 03.11.2012
Citation:
G. V. Nenashev, “On a bound on the chromatic number of almost planar graph”, Combinatorics and graph theory. Part V, Zap. Nauchn. Sem. POMI, 406, POMI, St. Petersburg, 2012, 95–106; J. Math. Sci. (N. Y.), 196:6 (2014), 784–790
Linking options:
https://www.mathnet.ru/eng/znsl5291 https://www.mathnet.ru/eng/znsl/v406/p95
|
Statistics & downloads: |
Abstract page: | 208 | Full-text PDF : | 71 | References: | 42 |
|