不含3圈和4圈的1-平面图是5-可染的

Every 1-planar graph without cycles of length 3 or 4 is 5-colorable

若图G能画到平面上,且允许每条边至多出现一个交叉点,则图G是1-平面图。图G的一个正常点染色是指存在一个顶点集到颜色集的映射φ:V(G)→{1,2,…,k},对于G中的任意两个相邻的点u和v,φ(u)≠φ(v)。图G的一个k染色是指图G能够正常点染色所需的色数至少为k,图G有一个k染色又称图G是k-可染的。通过权转移的方法证明了不含3圈和4圈的1-平面图是5-可染的。

A graph G is called 1-planar graph if it can be drawn on the plane so that each edge is crossed by at most one other edge. A propervertexcoloring of G is an assignment φ of integer to the vertex of G such that φ（u） ≠φ（v） if the vertex u and v adjacent in G. A k-coloring is a proper vertex coloring using k colors at least. The theorem that every 1- planar graph without cycles of length 3 or 4 is 5-colorable was given by the Discharging Method.