Article ID Journal Published Year Pages File Type
4649036 Discrete Mathematics 2010 9 Pages PDF
Abstract

Let mad(G) denote the maximum average degree (over all subgraphs) of GG and let χi(G)χi(G) denote the injective chromatic number of GG. We prove that if mad(G)≤52, then χi(G)≤Δ(G)+1χi(G)≤Δ(G)+1; and if mad(G)<4219, then χi(G)=Δ(G)χi(G)=Δ(G). Suppose that GG is a planar graph with girth g(G)g(G) and Δ(G)≥4Δ(G)≥4. We prove that if g(G)≥9g(G)≥9, then χi(G)≤Δ(G)+1χi(G)≤Δ(G)+1; similarly, if g(G)≥13g(G)≥13, then χi(G)=Δ(G)χi(G)=Δ(G).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,