Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647912 | Discrete Mathematics | 2012 | 6 Pages |
Abstract
An injective k-coloring of a graph GG is an assignment of kk colors to V(G)V(G) such that vertices having a common neighbor receive distinct colors. We study the list version of injective colorings of planar graphs. Let χil(G) and mad(G)mad(G) be the injective choosability number and the maximum average degree of GG, respectively. It is proved that (1) for each graph GG with mad(G)<103, χil(G)≤Δ(G)+4 if Δ(G)≥30Δ(G)≥30 (this conditionally improves some results of Doyon et al. (2010) [9] and Lužar et al. (2009) [11]), χil(G)≤Δ(G)+5 if Δ(G)≥18Δ(G)≥18, and χil(G)≤Δ(G)+6 if Δ(G)≥14Δ(G)≥14; (2) χil(G)≤Δ(G)+2 if mad(G)<3mad(G)<3 and Δ(G)≥12Δ(G)≥12 (this conditionally improves a result of Doyon et al. (2010) [9]).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Rui Li, Baogang Xu,