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

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

作　　者：郭春强 吴宝音都仍 GUO Chunqiang;WU Baoyindureng(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China)

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830017

出　　处：《新疆大学学报（自然科学版）（中英文）》2023年第3期267-273,共7页Journal of Xinjiang University(Natural Science Edition in Chinese and English)

基　　金：supported by National Natural Science Foundation of the People’s Republic of China“Research on the domination of regular graphs”(12061073)。

摘　　要：对于任何一个图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.

关 键 词：正常着色 奇着色 1-平面图 

分 类 号：O157.5[理学—数学]