Article ID Journal Published Year Pages File Type
4648815 Discrete Mathematics 2011 12 Pages PDF
Abstract

A vertex coloring of a graph GG is called injective if any two vertices joined by a path of length two get different colors. A graph GG is injectively kk-choosable if any list LL of admissible colors on V(G)V(G) of size kk allows an injective coloring φφ such that φ(v)∈L(v)φ(v)∈L(v) whenever v∈V(G)v∈V(G). The least kk for which GG is injectively kk-choosable is denoted by χil(G).Note that χil≥Δ for every graph with maximum degree ΔΔ. For planar graphs with girth gg, Bu et al. (2009) [15] proved that χil=Δ if Δ≥71Δ≥71 and g≥7g≥7, which we strengthen here to Δ≥16Δ≥16. On the other hand, there exist planar graphs with g=6g=6 and χil=Δ+1 for any Δ≥2Δ≥2. Cranston et al. (submitted for publication) [16] proved that χil≤Δ+1 if g≥9g≥9 and Δ≥4Δ≥4. We prove that each planar graph with g≥6g≥6 and Δ≥24Δ≥24 has χil≤Δ+1.

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