zbMATH — the first resource for mathematics

\(M\)-degrees of quadrangle-free planar graphs. (English) Zbl 1161.05024
The \(M\)-degree of an edge \(xy\) in a graph \(G\) is the maximum of the degrees of \(x\) and \(y\); the \(M\)-degree of \(G\) is the minimum over the \(M\)-degrees of its edges W. He, X. Hou, K.-W. Lih, J. Shao, W. Wang and X. Zhu [J. Graph Theory 41, No. 4, 307–317 (2002; Zbl 1016.05033)] showed that every planar graph without leaves of 4-cycles has \(M\)-degree at most 8. The present authors find that the maximum \(M\)-degrees for planar and projective planar graphs with no leaves of 4-cycles is 7; for such graphs on the torus or Klein bottle, the maximum is 8. Both bounds are sharp.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
PDF BibTeX Cite
Full Text: DOI
[1] Borodin, A generalization of Kotzig’s theorem and prescribed edge coloring of plane graphs, Math Notes Acad Sci USSR 48 pp 1186– (1990)
[2] Borodin, Structural theorem on plane graphs with application to the entire coloring, J Graph Theory 23 pp 233– (1996) · Zbl 0863.05035
[3] He, Edge-partitions of planar graphs and their game coloring numbers, J Graph Theory 41 pp 307– (2002) · Zbl 1016.05033
[4] Kotzig, Contribution to the theory of Eulerian polyhedra, Mat Čas 13 pp 20– (1963)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.