Abstract: The M-degree of an edge xy in a graph is the maximum of the degrees of x and y. The minimax degree of a graph G is the minimum of the M-degrees of its edges. In order to prove upper bounds on the game chromatic number, He, Hou, Lih, Shao, Wang, and Zhu showed that every planar graph G without leaves and 4-cycles has minimax degree at most 8 and gave an example of such a graph with minimax degree 3. This yields upper bounds on the game chromatic number of quadrangle-free planar graphs. We determine the maximum possible minimax degrees for planar, projective-planar and toroidal graphs without leaves and 4-cycles. In particular, for planar and projective-planar graphs this maximum is 7. This is joint work with O. Borodin, A. Kostochka and G. Yu. |