Portal de Periódicos da CAPES

MINIMAX DEGREES OF QUASIPLANAR GRAPHS WITH NO SHORT CYCLES OTHER THAN TRIANGLES

2008; Mathematical Society of the Republic of China (Taiwan); Volume: 12; Issue: 4 Linguagem: Inglês

10.11650/twjm/1500404982

2224-6851

O. V. Borodin, A. O. Ivanova, Alexandr Kostochka, Naeem N. Sheikh,

Graph Labeling and Dimension Problems

For an edge $xy$, let $M(xy)$ be the maximum of the degrees of $x$ and $y$. The {\em minimax degree} (or $M$-degree) of a graph $G$ is $M^*(G)=\min\{M(xy)| 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.