图的邻和可区别染色.docVIP

图的邻和可区别染色 李华龙，丁来浩，王光辉 山东大学数学学院，济南市，250100 摘要：给定图 G = (V, E)，图 G 的一个正常 [k]-边染色是一个映射 φ : E → {1, 2, . . . , k}，使 得 E 中任意一对相邻的元素染不同的颜色。我们用 f(v) 表示与点 v 相关联的边的颜色的加 和。图 G 的一个正常 [k]-邻和可区别边染色是一个 [k]-边染色，使得对任意一条边 uv E(G), f(u) = f(v)。在图 G 如上定义的染色中，我们将 k 的最小值称作 G 的邻和可区别边色数，记 为 χ (G)。相类似的，我们可以定义图的 [k]- 邻和可区别全染色，并将邻和可区别全色数记 为 χ (G)。计算机技术的迅速发展，大力推动了图论染色问题发展。近年来，图的邻和可区 别染色引起了学者们的广泛关注，本文主要介绍一下邻和可区别染色的一些进展和结论。 关键词：邻和可区别边染色，邻和可区别全染色，平面图 中图分类号： O157.5 Neighbor sum distinguishing colorings of graphs LI Hua-Long, Ding Lai-hao, WANG Guang-Hui Department of Mathematics, Shandong University, Jinan, 250100 Abstract: An edge [k]-coloring of a graph G is an edge coloring of G by using the color set [k] = {1, 2, · · · , k}. Let f(v) denote the sum of the colors of all incident edges of v. An edge [k]-neighbor sum distinguishing-coloring of G is an edge [k]-coloring of G such that for each edge uv ∈ E(G), f(u) = f(v). In such a coloring, the smallest value k is called neighbor sum distinguishing edge chromatic number, denoted by χ (G). Similarly, we can de?ne total [k]-neighbor sum distinguishing-coloring, and denote neighbor sum distinguishing total chromatic number by χ (G). The rapid development of computer technology vigorously promote the development of the coloring problem in graph theory. In recent years, neighbor sum distinguishing coloring attracted widespread attention, this article introduces some progress and conclusions about the neighbor sum distinguishing coloring. Key words: neighbor sum distinguishing edge coloring, neighbor sum distinguishing total coloring, planar graph  0  引言  作为离散数学的主要分支之一，图论具有重要的理论意义及实际意义。四色问题、中国邮 递员问题、哈密尔顿问题等都是图论中的经典问题，图论在计算机科学与技术、管理科学、通 基金项目： 国家自然科学基金，教育部高校博士点专项基金(20100131120017), 山东省优秀中青年奖励基 金(BS2012SF016) 作者简介： 通讯作者：李华龙(1988-) 男，硕士研究生，li6281878@126.com。 -1- 信工程等领域都有广泛的应用，用图论来解决运筹学、生物学、化学和信息计算机科学等学科 问题已显示出极大的优越性。它作为组合数学的一个重要分支，受到了各方面的普遍重视。 自二十世纪五十年代以来，计算机科学的迅速发展，有力地推动了图论的发展，关于图论 方面的结果大量涌现。十九世纪中叶，Frederick Guthrie 提出了著名的四色问题，其本质就是 图的染色问题