图论及其应用对图的均匀染色探究

开篇：润墨网以专业的文秘视角，为您筛选了一篇图论及其应用对图的均匀染色探究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要 对于图论研究而言，图的染色问题既是重点，又是热点。本文将围绕图的均匀染色问题展开相关探究，先后讨论了平面图的均匀染色、2-退化图的均匀染色以及图的全染色等。

关键词 图论 均匀染色 全染色

中图分类号：O157 文献标识码：A

1 均匀染色概述

对于图论研究而言，图的染色问题既是重点，又是热点。图的均匀染色属于一种相对特殊的图的染色问题，自诞生以来，在以工业生产的代表的诸多领域获得了广泛应用，在处理时间表问题、剖分问题以及承载平衡问题等方面发挥出了相当重要的作用。如进行工作安排时，同一个时间段内所要开展的工作将会受限于操作人员的数量。上述对色类大小的约束便促进了图的有界染色问题的提出和发展。对于图 而言，假设 为其某个正常状态下的顶点染色，若要求在 下，无论哪一个色类中的顶点数均不可超过，那么可将 当成是图的一个所谓的-界染色。若想予以强化，对每两个色类提出更高的要求，要求它们的顶点数差值必须控制在1以内，如此一来，便形成了本文所要探讨的图的均匀染色问题。很明显，对于图的一个均匀染色而言，也可将其当作图的一个[∣（） ∣/]-界染色。①

图的均匀染色，其特殊之处在于：k-可对图进行均匀染色，然而（k+1）-并非百分百具有这个性质。

2 图的均匀染色

2.1 平面图的均匀染色

设图属于平面图，人们习惯用（）来代表面的集合，在保证不会造成混淆的前提下，用表示（），并将其称之为面，且和周界上的诸点存在关联。所谓面 的度数（）指的是，和其存在关联关系的边的条数，其中，割边将会被计算2次。如果面的边界以一个圈的形态存在，那么该面被称之为简单面。在∈（）的情况下，习惯用（ ）来代表面 的闭途径，与此同时，用（ ）来代表和面存在关联关系的顶点集。如果b（ ）包含的各个顶点依次表示为，，…，，那么可记 =（…）。②如果平面的所有顶点均位于同一个没有界面的边界上，那么则被称之为外平面图。③

对平面图的均匀染色进行研究时，王维凡等人针对如下问题进行了研究：当（）赋值为5时，平面图的边列表染色将不涉及4-圈或者6-圈。从中可获得相应的启发，即对不涉及短圈的平面图的均匀染色这一类问题予以探究。

相关定理有：（1）每个不含5-圈的平面图均是由3-退化而来的；（2）若平面图不含3-圈、4-圈以及5-圈，那么对于任何一个≥{4，（）}而言，存在一个-均匀染色；（3）每个不含6-圈的平面图均是由3-退化得到的。

2.2 2-退化图的均匀染色

以如下定理及其证明为例。

定理：将（）的一个顶点记作，假设={，，…，}为的子集，同时符合∣（）∣≤（1≤≤），当满足-包含-均匀染色这一条件时，便能够得出也包含-均匀染色。④

证明：令=，同时令 = [（） ∪{}]（1≤≤），那么可得出、相等。将当作是包含的一个-均匀染色，此时色集可表示为={1，2，…，}。由于∣（）∣≤，那么将必然有这样一种颜色，能够使条件下的不和上述染色（即）的顶点保持相邻关系，此时，用完成的染色，则能够对的产生一个延拓效果，得到下的。考虑到∣（）∣≤，那么必然有一种以上的颜色∈{}，能够让条件下的不和的顶点保持相邻关系，接下来，用完成完成的染色，则能够对的产生一个延拓效果，得到下的。按照上述规则进行下去，直至将所涉及的诸多顶点全部赋予一种颜色，如此一来，便能够获得的一个所谓的-正常染色。很明显，对于所涉及的个顶点而言，各自所染颜色全部存在差异，如此可证明 为的一个所谓的-均匀染色。

3 图的均匀全染色

3.1 一类Mycielski图的均匀全色数

以如下定理及其证明为例。

定理：对+1阶星而言，可以得到如下结论（（））=（（））+1（≥2）。

证明：由于（（））=2，那么可知（（））≥2+1。现在仅需要对以下问题进行验证，即存在（（））的一个2+1-均匀全染色，并将其定义为图：（）=（（）） ∪{}，（） = （（（））/{}）∪{∣ = 0，2，3，...，}∪{， ∣ = 0，3，4，...，}∪{}。可得（）={，}，另外，G*中所具有的最大度点的导出图（即[]=）属于一条路，如此一来，可以得出：（）=（）=2，那么对于而言，存在一个2-均匀边染色，假设属于的一个2-均匀边染色，那么在这一条件的基础上，便可构造（）的一个点边全染色，记为，则有：（）=（），=0，2，3，…，；（）=（），=0，3，4，…，；（）=（）= （）=（）=2+1； （）= （）； （）= （）， ∈（（））/{}。很容易得出属于（）的一个点边全染色，同时∈{1，2，…，2+1}，另外，∣∣=3或者4。⑤所以，可以得出属于（）的一个2+1-均匀全染色。最终证得：（（））=（（））+1。

3.2 一些特殊平面图的均匀全色数

以平面图圈为研究对象，对其点边面均匀全染色问题予以研究。

定理：对圈（）（≥3），如果 =∣∣，那么可以得出（）=+2。

证明：对圈，假设其顶点分别是，，…，，边分别是，，…，那么可得到 = +1（=1，2，…），同时还能得到=，外部面用表示，内部面用表示。很明显，对于正常染色（任意）而言，和二者在颜色方面应是差异的，如此一来，对于任何一个均匀全染色而言，仅能使其色类最多包含两个元素，对于∪∪而言，当剔除、之后，将会剩下2个元素，所以，需种以上颜色，换而言之，（）≥+2。⑥接下来，基于为其构建+2-均匀全染色，那么有：%O（）=1，（）=2。将未经染色的那些元素按照下面的顺序进行排列：…，结合上述元素的先后顺序顺次使用3，4，…+2，3，4，…，+2进行染色，⑦如此一来，便可获得的一个正常状态下的+2-均匀全染色，也就是所谓的（）≤+2。最终证得（）=+2，证明完毕。

注释

① 李海伦.关于图的均匀染色理论的继续研究[D].山东大学，2010.

② 赵金丽.关于图的均匀染色[D].浙江师范大学，2011.

③ 赵金丽，卜月华.蛛形图的全图和中心图的均匀染色[J].浙江师范大学学报（自然科学版），2011.1：42-45.

④ 傅彩霞.若干倍图的均匀染色[J].浙江师范大学学报（自然科学版），2012.2：133-137.

⑤ 伍芳兰，左连翠.一类特殊笛卡尔积图的均匀染色[J].山东大学学报（理学版），2013.4：20-24.

⑥ 普昭年.若干倍图的均匀染色[J].河西学院学报，2009.5：11-14.

⑦ 朱俊蕾.退化图的均匀染色[J].嘉兴学院学报，2010.3：31-34+50.