Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419741 | Discrete Applied Mathematics | 2009 | 10 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yuehua Bu, Dong Chen, André Raspaud, Weifan Wang,