Equitable Coloring of IC-Planar Graphs with Girth g ≥ 7

An equitable k-coloring of a graph G is a proper vertex coloring such that the size of any two color classes differ at most 1. If there is an equitable k-coloring of G, then the graph G is said to be equitably k-colorable. A 1-planar graph is a graph that can be embedded in the Euclidean plane such that each edge can be crossed by other edges at most once. An IC-planar graph is a 1-planar graph with distinct end vertices of any two crossings. In this paper, we will prove that every IC-planar graph with girth g >= 7 is equitably Delta(G)-colorable, where Delta(G) is the maximum degree of G.

Automated summary

This paper investigates the equitable coloring problem of IC-planar graphs. By proving the theorem, we conclude that every IC-planar graph with a sufficiently large girth can be equitably colored.