An upper bound for the chromatic number of graphs with given thickness and girth

S. Sh. Adilov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: The thickness of a graph $G$ is the minimum number of planar graphs whose union is $G$. In this paper, we consider an upper bound for the chromatic number of graphs depending on thickness $k$ and girth $g$, where $k \ge 1$ and $g \ge 3$. In particular, for biplanar graphs with girth at least $10$ we obtain $5$-colorability.

Keywords: chromatic number, girth, thickness, planar graph, biplanar graph.