2017/06/07 by Mozafari-Nia, Mahsa, Omoomi, Behnaz · 1 citation
#05C10 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1706.02335
An injective coloring of a graph is a vertex coloring where two vertices with common neighbor receive distinct colors. The minimum integer k that G has a k-injective coloring is called injective chromatic number of G and denoted by χi(G). In this paper, the injective chromatic number of outerplanar graphs with maximum degree Δ and girth g is studied. It is shown that for every outerplanar graph, χi(G)≤ Δ+2, and this bound is tight. Then, it is proved that for outerplanar graphs with Δ=3, χi(G)≤ Δ+1 and the bound is tight for outerplanar graphs of girth three and 4. Finally, it is proved that, the injective chromatic number of 2-connected outerplanar graphs with Δ=3, g≥ 6 and Δ≥ 4, g≥ 4 is equal to Δ.