## 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 6 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.

Original language | English (US) |
---|---|

Pages (from-to) | 80-85 |

Number of pages | 6 |

Journal | Journal of Graph Theory |

Volume | 60 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2009 |

## Keywords

- Decomposition
- Degree
- Game coloring
- Planar graphs

## ASJC Scopus subject areas

- Geometry and Topology