In 1975, Melnikov conjectured that the edges and faces of each plane graph G may be colored with △(G)+3 colors so that any two adjacent or incident elements receive different colors, where △(G) is the maximum degree of G. Two similar, yet independent, proofs of this conjecture have been published recently by Waller (J. Combin. Theory Ser. B 69 (1997) 219) and Sanders and Zhao (Comnbinatorica 17 (1997) 441). Both proofs made use of the Four-Color Theorem. this paper presents a new proof of Melnikov's conjecture independent of the Four-Color Theorem.
展开▼
机译：1975年，梅尔尼科夫（Melnikov）推测，每个平面图G的边缘和面可以用△（G）+3种颜色着色，以便任何两个相邻或入射元素接收不同的颜色，其中△（G）是G的最大程度。 Waller（J. Combin。Theory Ser。B 69（1997）219）和Sanders and Zhao（Comnbinatorica 17（1997）441）最近发表了两个类似但独立的猜想的证明。两种证明都使用四色定理。本文提出了独立于四色定理的梅尔尼科夫猜想的新证明。
展开▼
