Injective coloring of planar graphs with girth 5

Yuehua BU; Piaopiao YE

doi:10.1007/s11464-022-1018-x

PDF(233 KB)

Front. Math. China ›› 2022, Vol. 17 ›› Issue (3) : 473-484. DOI: 10.1007/s11464-022-1018-x

RESEARCH ARTICLE

Injective coloring of planar graphs with girth 5

Yuehua BU¹^,² ,
Piaopiao YE¹

Author information +

History +

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 (G)$ of a graph $G$ is the least $k$ such that there is an injective $k$ -coloring. In this paper, we prove that for each planar graph with $g ≥ 5$ and $Δ (G) ≥ 20$ , $χ i (G) ≤ Δ (G) + 3$ .

Keywords

Planar graph / girth / injective coloring / face

Cite this article

EndNote

Ris (Procite)

Bibtex

Download citation ▾

Yuehua BU, Piaopiao YE. Injective coloring of planar graphs with girth 5. Front. Math. China, 2022, 17(3): 473‒484 https://doi.org/10.1007/s11464-022-1018-x

References

Publishing order | Descend order by publishing year | Descend order by cited within

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

[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 CrossRef Google scholar

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

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

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

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

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

[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 CrossRef Google scholar

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

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