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.

Keywords

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

RIGHTS & PERMISSIONS

Higher Education Press