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.
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
SN - 1027-5487
VL - 12
SP - 873
EP - 886
JO - Taiwanese Journal of Mathematics
JF - Taiwanese Journal of Mathematics
IS - 4
ER -