























Listed as No. 53 among the one hundred famous unsolved problems in [J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, Berlin, 2008] is Steinberg's conjecture, which states that every planar graph without 4- and 5-cycles is 3-colorable. In this paper, we show that plane graphs without 4- and 5-cycles are 3-colorable if they have no ext-triangular 7-cycles. This implies that (1) planar graphs without 4-, 5-, 7-cycles are 3-colorable, and (2) planar graphs without 4-, 5-, 8-cycles are 3-colorable, which cover a number of known results in the literature motivated by Steinberg's conjecture.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。