专业校色参照图
高校应用数学学报 2018, 33(3): 324-330 近完全图的邻点可区别正常边色数 陈祥恩^李泽鹏2** (1.西北师范大学数学与统计学院，甘肃兰州730070; 2.兰州大学信息科学与工程学院，甘肃兰州730000) 摘要：引入了近完全图的概念，并根据其结构特征，给出了近完全图的邻点可区别 正常边色数.该结果揭示了完全图中删去一个匹配后其邻点可区别正常边色数的变化 情况. 关键词：完全图；近完全图；匹配；邻点可区别正常边染色；邻点可区别正常边色数 中图分类号：O157.5 文献标识码：A文章编号：1000-4424(2018)03-0324-07 §1引言 设G为有限，无向的简单图，5(G),A(G)分别表示G的最小度和最大度，C= {1，2,...，fc}为 颜色集合.设映射/ ：丑(G)C是图G的一个fc-正常边染色，对任意的r e ^(G)，令57(4 = {/(_) |_e E(G)},称㈦为顶点r在/下的色集合.记及七）=C-5>(外若G中任意相邻 顶点的色集合不同，即对e y(G)，_e E(G),有57⑷=SV(r)(即=5^))，贝/称 为G的fc-邻点可区别正常边染色(简称为fc-A V D P E C),数x;(G) =m in{fc |G有一个fc-A V D P E C}称为G的邻点可区别正常边色数. 图的点可区别正常边染色在文献[1-2]中已研究过.张忠辅等在文[3]中提出了图的邻强边染 色(即邻点可区别正常边染色)的概念，并对一些特殊图类做了研究，同时给出了下面的猜想. 猜想1.1[3]设G为阶数至少是6的简单连通图，则尨(G)S A(G)+2. 围绕猜想1.1，图的邻点可区别正常边染色问题被广泛研究.B a lis te r等在文[4]中证明了猜 想1.1对二部图或最大度不超过3的图成立；W ang等在文[5]中证明了猜想1.1对最大度大于3且 最大平均度小于3的图成立.H o rn a k,H uang和W ang在文[6]中证明了猜想1.1对A(G)212的平面图G成立.对于一般图，H a ta m i在文[7]中利用概率方法得到了对A(G)>1020的图G,有尨(G)S A(G)+300.此结果被W ang和L i间改进到尨(G)S A(G)+180,其中A(G) > 1015. W ang等在文[9]中证明了x K G)S 2.5A(G)；此后被VuCkovi#0]改进到2A(G)+2.另外，也有 收稿日期：2017-10-25 修回日期：2018-02-02 *通讯作者，E-mail:lizp@https://www.doczj.com/doc/bc7143895.html, 基金项目：国家自然科学基金(11761064; 61672050; 61163037);兰州大学中央高校基本科研业务费专项资金(lzujbky-2018-37)
第38卷 第4期 高 师 理 科 学 刊 Vol. 38 No.4 2018年 4月 Journal of Science of Teachers′College and University Apr. 2018 文章编号：1007-9831（2018）04-0001-03 图色数的一种求法 杨雅琴 （齐齐哈尔大学 理学院，黑龙江 齐齐哈尔 161006） 摘要：利用组合数学中图转化成树的思想，从图中一顶点出发，按照图的邻接矩阵中各顶点间边存在的情况，建立各级树，根据要着色的顶点与已着色顶点间边存在的情况，给所要着色的顶点着色．当所有顶点都已着色后，所用颜色个数就是图的色数． 关键词：图；邻接矩阵；树；色数 中图分类号：O157 文献标识码：A doi：10.3969/j.issn.1007-9831.2018.04.001 A method for calculating the chromatic number of a graph YANG Ya-qin （School of Science，Qiqihar University，Qiqihar 161006，China） Abstract：Using combinatorial mathematics graph into a tree，starting from a vertex in that graph，builds trees at all levels according to the existence of edges between vertices in the adjacency matrix of graphs．According to the existence of coloring vertices and coloured vertex edges，color the vertices which need to be colored．The number of colors used is the chromatic number of the graph when all vertices are colored. Key words：graph；adjacency matrix；tree；chromatic number 近年来，对于图着色的研究有许多[1-6]，但关于图色数的求法并不多，多数文献是研究图的邻点可区别全色数的上界和图的一般邻点可区别全染色问题．本文借助利用组合数学中图转化成树的思想，从图中一顶点出发，按照图的邻接矩阵中各顶点间边存在的情况，建立各级树，根据要着色的顶点与已着色顶点间边存在的情况，给所要着色的顶点着色，当所有顶点都已着色后计算所用颜色个数就是图的色数． 定义[1]251 设G 是n 阶一般图，并令其顶点12, , , n a a a L 按某种顺序排列．A 是一个n n ′的矩阵，其第i 行第j 列元素ij a 等于连接顶点i a 和j a 的边的数目(1, )i j n ￡￡．于是，总有ij ji a a =，而且ii a 等于顶点i a 处的环的个数，这样的矩阵A 称为G 的邻接矩阵． 算法 已知图G 所包含点的集合V 和所有边的集合E ，以及用来给图中各点着色的k 种颜色构成的集合{}12, , , k T B B B =L ． Step1 根据图G 所包含点的集合V 和所有边的集合E ，得出图G 的邻接矩阵A ． Step2 设S 表示点集V 中已被着色的点构成的集合，M 表示已给点着色的颜色构成的集合，初始值{}, {}S M ==． Step3 设从点集V 中点1a 开始着色，给点1a 着1B 色，则{}{}11, S S a M M B ==U U ． Step4 以点1a 为树根，根据邻接矩阵A 中点1a 所对应行中元素值为1所对应点的情况，建立二级树 收稿日期：2017-08-10 基金项目：齐齐哈尔大学校教研项目（2017030） 作者简介：杨雅琴（1971-），女，吉林白城人，副教授，硕士，从事应用数学研究．E-mail：yyqcpy2008 @https://www.doczj.com/doc/bc7143895.html,