Minimax degrees of quasiplanar graphs with no short cycles other than triangles

Oleg V. Borodin, Anna O. Ivanova, Alexandr V. Kostochka, Naeem N. Sheikh

Research output: Contribution to journalArticlepeer-review

Abstract

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)|xy ∈ 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.

Original languageEnglish (US)
Pages (from-to)873-886
Number of pages14
JournalTaiwanese Journal of Mathematics
Volume12
Issue number4
DOIs
StatePublished - Jul 2008

Keywords

  • Decomposition
  • Planar graphs
  • Short cycles

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Minimax degrees of quasiplanar graphs with no short cycles other than triangles'. Together they form a unique fingerprint.

Cite this