Portal de Periódicos da CAPES

M ‐degrees of quadrangle‐free planar graphs

2008; Wiley; Volume: 60; Issue: 1 Linguagem: Inglês

10.1002/jgt.20346

1097-0118

O. V. Borodin, Alexandr Kostochka, Naeem N. Sheikh, Gexin Yu,

Computational Geometry and Mesh Generation

Abstract The M‐degree of an edge xy in a graph is the maximum of the degrees of x and y . The M‐degree of a graph G is the minimum over M ‐degrees of its edges. In order to get upper bounds on the game chromatic number, He et al showed that every planar graph G without leaves and 4‐cycles has M ‐degree at most 8 and gave an example of such a graph with M ‐degree 3. This yields upper bounds on the game chromatic number of C 4 ‐free planar graphs. We determine the maximum possible M ‐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. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 80–85, 2009