List injective colorings of planar graphs
List injective colorings of planar graphs
复制标题
DOI：
10.1016/j.disc.2010.10.008
复制
发表时间：
2011-02-06
影响因子：
0.8
通讯作者：
Ivanova, A. O.
中科院分区：
文献类型：
--
作者：
Borodin, O. V.;Ivanova, A. O.
图\(C\)的一个顶点着色如果使得由长度为\(2\)的路径相连的任意两个顶点具有不同颜色，则被称为单射的。如果图\(G\)的顶点集\(V(G)\)上的任意一个大小为\(k\)的可允许颜色列表\(L\)都允许一种单射着色\(\varphi\)，使得对于任意\(\nu\in V(G)\)都有\(\varphi(\nu)\in L(\nu)\)，那么图\(G\)是单射\(k\)-可选择的。使得图\(G\)是单射\(k\)-可选择的最小的\(k\)记为\(\chi_{l}^{(j)}(G)\)。注意对于每一个最大度为\(\Delta\)的图都有\(\chi_{l}^{(j)}\geq\Delta\)。对于围长为\(g\)的平面图，卜等人（2009年）[15]证明了如果\(\Delta\geq71\)且\(g\geq7\)，则\(\chi_{l}^{(j)}=\Delta\)，在此我们将其加强为\(\Delta\geq16\)。另一方面，对于任意\(\Delta\geq2\)，存在围长\(g = 6\)且\(\chi_{l}^{(j)}=\Delta + 1\)的平面图。克兰斯顿等人（已投稿）[16]证明了如果\(g\geq9\)且\(\Delta\geq4\)，则\(\chi_{l}^{(j)}<\Delta + 1\)。我们证明对于每一个围长\(g\geq6\)且\(\Delta\geq24\)的平面图都有\(\chi_{l}^{(j)}\)（此处原文似乎不完整）
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)