IC-planar graphs are odd-10-colorable

• Published in: Applied mathematics and computation 2023-08, Vol.451, p.128020, Article 128020
• Main Authors: Pan, Chenran, Wang, Weifan, Liu, Runrun
• Format: Article
• Language: English
• Subjects: Discharging; IC-planar graph; Odd coloring; Reducible configuration
• ISSN: 0096-3003; 1873-5649
• DOI: 10.1016/j.amc.2023.128020

•We prove that for every IC-planar graph G,χ0(G)≤10. This new result gives an upper bound of the odd chromatic number for IC-planar graphs. As far as we know, this bound is best possible.•We apply the discharging method to the coloring problem of an IC-planar graph G by constructing a plane graph associate to G.•The concept of odd coloring was introduced by Petrušsevski and Skrekovski in 2021. So the study of this new coloring is in the beginning stage. We provide a method to do research in this area. An odd-k-coloring of a graph G is a proper k-coloring such that for every vertex v∈V(G) with d(v)≥1, there exists a color occurring odd times in its neighbors. The odd chromatic number, denote by χo(G), of G is the smallest integer k so that G admits an odd-k-coloring. Call a graph G IC-planar if it can be drawn in the plane so that every edge is crossed by at most once and every vertex has at most one incident edge being crossed. It was shown that every planar graph G has χo(G)≤8. In this paper we show that every IC-planar graph G satisfies χo(G)≤10.