点染色和边赋权

Vertex-Colors and Edge-Weights

Lyngsie,Thomassen和Zhong 在1-2-3-猜想的基础上提出了一个强化4-色定理的猜想:对于任意不含孤立边的平面图G,存在G的一个边赋权,使得对任意相邻的两个顶点u,v,有 我们称满足上述条件的边赋权w为G的一个3-边赋权4-染色。这是一个比4-色定理强很多的猜想。在本文中我们证明了阶数至少为3的树满足这个猜想。另外,利用4-色定理,我们证明了每一个平面图 存在一个4-边赋权4-染色。

Lyngsie,Thomassen and Zhong on the base of 1-2-3-conjection proposed a conjecture that strengthens the four-color theorem:Every graph G with no isolated edges has a mapping,so that for any two adjacent vertices u and v,We say satisfy the above conditions edge weighting w is 3-edge weighting 4-coloring of a graph G.This conjecture is considerably stronger than the four-color theorem.In this paper,we prove that Lyngsie,Thomassen and Zhong conjecture holds for trees.By using the four-color theorem,we prove that every planar graph has a 4-edge weighting 4-coloring.