List injective colorings of planar graphs

作者：Borodin O V^*; Ivanova A O

来源：Discrete Mathematics, 2011, 311(2-3): 154-165.

DOI：10.1016/j.disc.2010.10.008

• Planar graph
• Injective coloring
• Girth

A vertex coloring of a graph C is called injective if any two vertices joined by a path of length two get different colors. A graph G is injectively k-choosable if any list L of admissible colors on V(G) of size k allows an injective coloring phi such that phi(nu) is an element of L(nu) whenever nu is an element of V(G). The least k for which G is injectively k-choosable is denoted by chi(l)(j)(G).
Note that chi(l)(j) >= Delta for every graph with maximum degree Delta. For planar graphs with girth g, Bu et al. (2009) [15] proved that chi(l)(j) = Delta if Delta >= 71 and g >= 7, which we strengthen here to Delta >= 16. On the other hand, there exist planar graphs with g = 6 and chi(l)(j) = Delta + 1 for any Delta >= 2. Cranston et al. (submitted for publication) [16] proved that chi(l)(j) < Delta + 1 if g >= 9 and Delta >= 4. We prove that each planar graph with g >= 6 and Delta >= 24 has chi(l)(j) <= Delta + 1.

• 出版日期2011-2-6