2025/04/17 by Weichan Liu, Liu, Weichan
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2504.12647
openalex publication_date 2025/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An equitable coloring of a graph is a proper coloring where the sizes of any two different color classes do not differ by more than one. A graph is IC-planar if it can be drawn in the plane so that no two crossed edges have a common endpoint, and is NIC-planar graphs if it can be embedded in the plane in such a way that no two pairs of crossed edges share two endpoints. Zhang proved that every IC-planar graph with maximum degree Δ≥ 12 and every NIC-planar graph with maximum degree Δ≥ 13 have equitable Δ-colorings. In this paper, we reduce the threshold from 12 to 10 for IC-planar graphs and from 13 to 11 for NIC-planar graphs.