1-平面图的奇着色数最多是21

Odd Chromatic Number of a 1-Planar Graph is at Most 21

对于任何一个图G的正常点着色φ而言,如果对于任何一个非孤立点x,存在一个颜色c使得|φ^(-1)(c)∩N_(G)(x)|是奇的,则φ被称为图G的奇着色.如果一个图能画在一个平面上,使得每一边至多被另一条边相交,则这样的图被称为1-平面图.证明了任何一个1-平面图是奇21-着色的,改进了最近由Cranston,Lafferty和Song得到的界23.

A proper vertex coloringφof a graph G is said to be odd if for each non-isolated vertex x∈V(G)there exists a color c such that|φ~(-1)(c)∩N_G(x)|is odd.A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge.We prove every 1-planar graph admits an odd 21-coloring.This improves a recently obtained bound,23,due to Cranston,Lafferty and Song.