图的邻和可区别染色李华龙，丁来浩，王光辉山东大学数学学院，济南市，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.5NeighborsumdistinguishingcoloringsofgraphsLIHua-Long,DingLai-hao,WANGGuang-HuiDepartmentofMathematics,ShandongUniversity,Jinan,250100Abstract:Anedge[k]-coloringofagraphGisanedgecoloringofGbyusingthecolorset[k]={1,2,···,k}.Letf(v)denotethesumofthecolorsofallincidentedgesofv.Anedge[k]-neighborsumdistinguishing-coloringofGisanedge[k]-coloringofGsuchthatforeachedgeuv∈E(G),f(u)=f(v).Insuchacoloring,thesmallestvaluekiscalledneighborsumdistinguishingedgechromaticnumber,denotedbyχ(G).Similarly,wecandefinetotal[k]-neighborsumdistinguishing-coloring,anddenoteneighborsumdistinguishingtotalchromaticnumberbyχ(G).Therapiddevelopmentofcomputertechnologyvigorouslypromotethedevelopmentofthecoloringproblemingraphtheory.Inrecentyears,neighborsumdistinguishingcoloringattractedwidespreadattention,thisarticleintroducessomeprogressandconclusionsabouttheneighborsumdistinguishingcoloring.Keywords:neighborsumdistinguishingedgecoloring,neighborsumdistinguishingtotalcoloring,planargraph0引言作为离散数学的主要分支之一，图论具有重要的理论意义及实际意义。四色问题、中国邮递员问题、哈密尔顿问题等都是图论中的经典问题，图论在计算机科学与技术、管理科学、通---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---基金项目：国家自然科学基金(11101243)，教育部高校博士点专项基金(20100131120017),山东省优秀中青年奖励基金(BS2012SF016)作者简介：通讯作者：李华龙(1988-)男，硕士研究生，li6281878@126.com。-1----本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---信工程等领域都有广泛的应用，用图论来解决运筹学、生物学、化学和信息计算机科学等学科问题已显示出极大的优越性。它作为组合数学的一个重要分支，受到了各方面的普遍重视。自二十世纪五十年代以来，计算机科学的迅速发展，有力地推动了图论的发展，关于图论方面的结果大量涌现。十九世纪中叶，FrederickGuthrie提出了著名的四色问题，其本质就是图的染色问题，四色问题也因此成为了图的染色问题的起源。从此越来越多的学者开始关注图的染色问题，图的染色理论得以迅速发展并成为图论的经典内容。图的染色理论不仅具有重要的理论意义，而且具有很强的应用背景，数据传输、网络设计、交通流等问题都可以归结到染色问题中来解决。图的染色理论存在很多分支，一般可将其分为点染色、边染色、全染色以及在此基础上添加其他约束所产生的一些特殊染色。本文主要介绍了邻和可区别染色的一些进展和结论。本文中用到但没有定义的符号和术语可以在[1]中找到。对于图G我们用V(G)，E(G)，和∆(G)分别表示图G的点集、边集、最大度。1图的点染色、边染色及全染色给定一个图G=(V,E)和一个正整数k，图G的一个正常k-顶点染色是一个映射φ:V(G)→{1,2,...,k}使得对每一对相邻的顶点u,v有φ(u)=φ(v)，这时我们称图G是k-可染的。图G的色数χ(G)是指使得图G是k-可染的k的最小值。是否每一个地图都可以被四种颜色染色使得相邻区域染不同的颜色？这就是著名的四色猜想。当我...