TY - JOUR

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

AU - Borodin, Oleg V.

AU - Ivanova, Anna O.

AU - Kostochka, Alexandr V.

AU - Sheikh, Naeem N.

N1 - Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 2008/7

Y1 - 2008/7

N2 - 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.

AB - 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.

KW - Decomposition

KW - Planar graphs

KW - Short cycles

UR - http://www.scopus.com/inward/record.url?scp=77952189127&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77952189127&partnerID=8YFLogxK

U2 - 10.11650/twjm/1500404982

DO - 10.11650/twjm/1500404982

M3 - Article

AN - SCOPUS:77952189127

VL - 12

SP - 873

EP - 886

JO - Taiwanese Journal of Mathematics

JF - Taiwanese Journal of Mathematics

SN - 1027-5487

IS - 4

ER -