|国家预印本平台
首页|Equitable coloring of graphs beyond planarity

Equitable coloring of graphs beyond planarity

Equitable coloring of graphs beyond planarity

来源:Arxiv_logoArxiv
英文摘要

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 $\Delta\geq 12$ and every NIC-planar graph with maximum degree $\Delta\geq 13$ have equitable $\Delta$-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.

Weichan Liu

数学

Weichan Liu.Equitable coloring of graphs beyond planarity[EB/OL].(2025-04-17)[2025-05-24].https://arxiv.org/abs/2504.12647.点此复制

评论