M-degrees of quadrangle-free planar graphs

Oleg V. Borodin, Alexandr V. Kostoehka, Naeem N. Sheikh, Gexin Yu

Research output: Contribution to journalArticlepeer-review


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 C4-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 languageEnglish (US)
Pages (from-to)80-85
Number of pages6
JournalJournal of Graph Theory
Issue number1
StatePublished - Jan 2009


  • Decomposition
  • Degree
  • Game coloring
  • Planar graphs

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint Dive into the research topics of 'M-degrees of quadrangle-free planar graphs'. Together they form a unique fingerprint.

Cite this