Equitable Coloring of IC-Planar Graphs with Girth <i>g</i> ≥ 7

Abstract

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 Δ(G)-colorable, where Δ(G) is the maximum degree of G.

Keywords

• equitable k-coloring
• IC-planar graph
• discharging method
• girth