Publications
Sort:
Issue
Odd Chromatic Number of a 1-Planar Graph is at Most 21
Journal of Xinjiang University(Natural Science Edition in Chinese and English) 2023, 40(3): 267-273
Published: 01 May 2023
Abstract PDF (3.7 MB) Collect
Downloads:25

A proper vertex coloring φ of a graph G is said to be odd if for each non-isolated vertex xV(G) there exists a color c such that |φ−1(c)∩NG(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.

Total 1