×

zbMATH — the first resource for mathematics

Minimax degrees of quasiplanar graphs with no short cycles other than triangles. (English) Zbl 1163.05013
Summary: 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)\mid xy\in 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.

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI