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

图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.

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

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 xli (G).Let G be a graph embedded in a surface Σ of Euler characteristic x(Σ)≥0 with maximum degree Δ and girth g.We prove that xli (G)≤A+3 if A≥7 and g≥6.