关于可嵌入曲面图的列表(d,1)-全标号问题.docVIP

n 关于可嵌入曲面图的列表 (d,1)-全标号问题 于永，张欣，刘桂真 山东大学数学学院，济南　 250100 摘要：一个图 G 的 k-(d,1)-全标号是一个从集合 V (G) E(G) 到颜色集 {0, 1, · · · , k} 的一个 映射 c，使得当 uv E(G) 时满足 c(u) ?= c(v)；当 e 与 e′ 是两条相邻的边时满足 c(e) ?= c(e′)；当 u 是关联边 e 的一个点时满足 |c(u) ? c(e)| ≥ d。使得图 G 具有 k-(d,1)-全标 号的最小整数 k 称为 (d,1)-全标号数，记为 λTd (G)。对于每个元素 x V (G) ∪ E(G)，设 L(x) （其中 |L(x)| = k）是一个赋予 x 的颜色列表。如果 G 具有一个 (d,1)-全标号 c 使得 c(x) L(x) 对每个 x V (G) ∪ E(G) 成立，则称 c 为 G 的一个列表 k-(d,1)-全标号或 G 是列 表 k-(d,1)-全可标号的。使得图 G 具有列表 k-(d,1)-全标号的最小整数 k 称为列表 (d,1)-全标 号数，记为 ChTd,1(G)。本文研究了最大度充分大的可嵌入曲面图的列表 (d,1)-全标号问题并证 明了其列表 (d,1)-全标号数不超过 ?(G) + 2d。 关键词：图论；(d,1)-全标号；列表 (d,1)-全标号；列表 (d,1)-全标号数 中图分类号： O157.5 List (d,1)-total labelling of graphs embedded in surfaces YU Yong, ZHANG Xin, LIU Gui-Zhen School of Mathematics, Shandong University, Jinan 250100 Abstract: A k-(d,1)-total labelling of a graph G is a function c from V (G) ∪ E(G) to the color set {0, 1, · · · , k} such that c(u) ?= c(v) if uv ∈ E(G), c(e) ?= c(e′) if e and e′ are two adjacent edges, and |c(u) ? c(e)| ≥ d if vertex u is incident to the edge e. The minimum k such that G has a k-(d,1)-total labelling is called the (d,1)-total labelling number and denoted by λTd (G). Suppose that L(x) is a list of colors available to choose for each element x ∈ V (G) ∪ E(G). If G has a (d,1)-total labelling c such that c(x) ∈ L(x) for all x ∈ V (G) ∪ E(G), then we say that c is an L-(d,1)-total labelling of G, and G is L-(d,1)-total labelable. The list (d,1)-total labelling number, denoted by ChTd,1(G), is the minimum k such that G is k-(d,1)-total labelable. In this paper, we prove that the list (d,1)-total labelling number of a graph embedded in a surface with Euler characteristic ε whose maximum degree ?(G) is su?ciently large is at most ?(G) + 2d. Key words: graph theory; (d,1)-total labelling; list (d,1)-total labelling; list (d,1)-total 基金项目： GIIFSDU Foundation (yzc11025), RFDP Foundation (200804220001, 20100131120017), NNSF Foundation 作者简介： Yu Yong (1985-), male, PH.