1-平面图的奇着色数最多是21（英文）

doi:10.13568/j.cnki.651094.651316.2022.07.01.0001

新疆大学学报（自然科学版中英文） ›› 2023, Vol. 40 ›› Issue (03) : 267-273. DOI: 10.13568/j.cnki.651094.651316.2022.07.01.0001

1-平面图的奇着色数最多是21（英文）

郭春强, 吴宝音都仍

作者信息 +

History +

摘要

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