Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649036 | Discrete Mathematics | 2010 | 9 Pages |
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
Daniel W. Cranston, Seog-Jin Kim, Gexin Yu,