Article ID Journal Published Year Pages File Type
4647912 Discrete Mathematics 2012 6 Pages PDF
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
, ,