Injective coloring of planar graphs with girth 5

Abstract

A coloring of a graph G is injective if its restriction to the neighbour of any vertex is injective. The injective chromatic number X_i\left(G\right) of a graph G is the leastk such that there is an injective k-coloring. In this paper, we prove that for each planar graph with g\ge 5 and \Delta \left(G\right)\ge 20, {\chi }_i\left(G\right)\le \Delta \left(G\right)+3.

Key words： Planar graph; girth; injective coloring; face

References

1 Bu Y H, Chen D, Raspaud A, Wang W. Injective coloring of planar graphs. Discrete Appl. Math., 2009, 157(4): 663–672

2 Bu Y H, Lu K. List injective coloring of planar graphs with girth 5, 6, 8. Discrete Appl. Math., 2013, 161(10/11): 1367–1377

3 Cranston D, Kim S, Yu G X. Injective colorings of graphs with low average degree. Algorithmica, 2010, 60(3): 553–568

4 Cranston D, Kim S, Yu G X. Injective colorings of sparse graphs. Discrete Math., 2010, 310(21): 2965–2973

5 Dong W, Lin W S. Injective coloring of planar graphs with girths 6. Discrete Math., 2013, 313(12): 1302–1311

6 Dong W, Lin W S. Injective coloring of planar graphs with girths 5. Discrete Math., 2014, 315/316(12): 120–127

7 Doyon A, Hahn G, Raspaud A. Some bounds on the injective chromatic number of graphs. Discrete Math., 2012, 310(6): 585–590

8 Hahn G, Kratochvíl J, Širáň J, Sotteau D. On the injective chromatic number of graphs. Discrete Math., 2002, 256(1/2): 179–192

9 Li R, Xu B G. Injective choosability of planar graphs of girth five and six. Discrete Math., 2012, 312(9): 1260–1265

10 Lužar B, Škrekovski S, Tancer M. Injective colorings of planar graphs with few colors. Discrete Math., 2009, 309(18): 5636–5649