1-planar Graphs without 4-cycles or 5-cycles are 5-colorable

• 作者: Li-li SONG Lei SUN
• 来源期刊: 应用数学学报（英文版）
• 年，卷（期）: 2022,（1）
• 页码范围: 169-177
• 页数: 9页
• 语种: 英文

摘要

A graph is 1-planar if it can be drawn on the Euclidean plane so that each edge is crossed by at most one other edge.A proper vertex k-coloring of a graph G is defined as a vertex coloring from a set of k colors such that no two adjacent vertices have the same color.A graph that can be assigned a proper k-coloring is k-colorable.A cycle is a path of edges and vertices wherein a vertex is reachable from itself.A cycle contains k vertices and k edges is a k-cycle.In this paper,it is proved that 1-planar graphs without 4-cycles or 5-cycles are 5-colorable.