Injective coloring of planar graphs with girth 5

Abstract

A $ k $-injective-coloring of a graph $ G $ is a mapping $ c: \; V\left(G \right) \to \left\{ {1, 2, \cdots, k} \right\} $ such that $ c\left(u \right) \ne c\left(v \right) $ for any two vertices $ u $ and $ v $ if $ u $ and $ v $ have a common vertex. The injective chromatic number of $ G $, denoted by $ {\chi _i}\left(G \right) $, is the least $ k $ such that $ G $ has an injective k-coloring. In this paper, we prove that for planar graph $ G $ with $ g\left(G \right) \ge 5 $, $ \Delta \left(G \right) \ge 20 $ and without adjacent 5-cycles, $ {\chi _i}\left(G \right) \le \Delta \left(G \right) + 2 $.

Keywords

• injective coloring
• planar graph
• cycle