围长至少为6的曲面图的列表单射染色

The List Injective Coloring of Embedded Graphs with Girth at Least Six

图G的一个点染色称为单射染色,如果任何两个有公共邻点的顶点染不同的颜色.一个图G称为单射k-可选择的,如果对于顶点V(G)的任何一个大小为k的允许颜色列表L,都存在一个单射染色φ,使得对于v∈V(G),有φ(v)∈L(v).使得G为单射k-可选择的最小k,称为G的列表单射染色数,记作χ_i^l(G).设G是最大度为Δ,围长为g的可嵌入到欧拉示性数χ(Σ)≥0的曲面Σ的一个图.证明了若Δ≥7且g≥6,则χ_i^l(G)≤Δ+3.

A vertex coloring of a graph G is called injective if any two vertices with a common neighbor receive distinct 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 φ such that φ（ v） ∈L（ v） whenever v∈V（ G）. The least k for which G is injectively k-choosable is called the list injective coloring number of G,and denoted by χi^l（ G）. Let G be a graph embedded in a surface Σ of Euler characteristic χ（ Σ） ≥0 with maximum degree Δ and girth g. We prove that χi^l（ G） ≤Δ ＋3 if Δ≥7 and g≥6.