# zbMATH — the first resource for mathematics

Minimax degrees of quasiplanar graphs with no short cycles other than triangles. (English) Zbl 1163.05013
Summary: For an edge $$xy$$, let $$M(xy)$$ be the maximum of the degrees of $$x$$ and $$y$$. The minimax degree (or $$M$$-degree) of a graph $$G$$ is $$M^*(G)= \min\{M(xy)\mid xy\in E(G)\}$$. In order to get upper bounds on the game chromatic number of planar graphs, He, Hou, Lih, Shao, Wang, and Zhu showed that every planar graph $$G$$ without leaves and 4-cycles has minimax degree at most 8, which was improved by Borodin, Kostochka, Sheikh, and Yu to the sharp bound 7. We show that every planar graph $$G$$ without leaves and 4- and 5-cycles has $$M$$-degree at most 5, which bound is sharp. We also show that every planar graph $$G$$ without leaves and cycles of length from 4 to 7 has $$M$$-degree at most 4, which bound is attained even on planar graphs with no cycles of length from 4 to arbitrarily large number. Besides, we give sufficient conditions for a planar graph to have $$M$$-degrees 3 and 2. Similar results are obtained for graphs embeddable into the projective plane, the torus and the Klein bottle.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text: