Article ID Journal Published Year Pages File Type
419741 Discrete Applied Mathematics 2009 10 Pages PDF
Abstract

A coloring of a graph GG is injective if its restriction to the neighborhood of any vertex is injective. The injective chromatic number  χi(G)χi(G) of a graph GG is the least kk such that there is an injective kk-coloring. In this paper we prove that if GG is a planar graph with girth gg and maximum degree ΔΔ, then (1) χi(G)=Δχi(G)=Δ if either g≥20g≥20 and Δ≥3Δ≥3, or g≥7g≥7 and Δ≥71Δ≥71; (2) χi(G)≤Δ+1χi(G)≤Δ+1 if g≥11g≥11; (3) χi(G)≤Δ+2χi(G)≤Δ+2 if g≥8g≥8.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,