乘积图的多彩着色

发布时间：2020-04-22 15:01

【摘要】：图的顶点着色是图论中的重要研究专题,在实际生活中有着极其广泛的应用.诸如学生选课,四色问题,会议安排,中继站分配特别是计算机网络方面许多问题都能转化为顶点着色问题.图的r-多彩着色是正常顶点着色,且满足每个度数为d(v)的顶点其邻点的颜色数至少为min{d(v),r}.它把图的正常着色(1-多彩着色),动态着色(2-多彩着色),平方着色(△-多彩着色)都包括在内,是一种非常有意义的新着色.确定一个图能否进行r-多彩着色的最小颜色数也就是r-多彩色数,是该专题研究的首要任务.圈和路是最基本的图类,文献[1]中给出了它们最基本的结论.图G的l次方Gl是图的基本概念,其顶点与图G相同,两个顶点相邻当且仅当是图G中两个顶点的距离不超过l.本文首先讨论了路和圈的l次方多彩色数,并且研究了平方圈和平方路的r-多彩色数.笛卡尔积和强积作为图运算的基本形式,在[8],[10],[12,13]中作者研究了有关乘积图的多彩色数和r-多彩色数.在此基础上,本文研究平方圈,平方路与路的笛卡尔积,路与路,路与圈强积图的多彩色数和r-多彩色数并得到一些比较好的结论.本文中主要通过证明图的多彩着色数,r-多彩色数的上下界相等而获得确切值,其中上界是通过运用相关代数运算给出具体着色方式而获得的,下界是通过反证法及严密推理得到的.
【学位授予单位】：天津师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 Shun-yi LIU;He-ping ZHANG;Hong-liang LU;Yu-qing LIN;;A Note on the Strong Edge-coloring of Outerplanar Graphs with Maximum Degree 3[J];Acta Mathematicae Applicatae Sinica;2016年04期

2 WAN Min;XU BaoGang;;Acyclic edge coloring of planar graphs without adjacent cycles[J];Science China(Mathematics);2014年02期

3 ;Acyclic edge coloring of graphs with large girths[J];Science China(Mathematics);2012年12期

4 ;Total coloring of embedded graphs of maximum degree at least ten[J];Science China(Mathematics);2010年08期

5 ;Proofs for some known results of equitable coloring[J];商丘师范学院学报;2008年09期

6 乐启炽 ,崔建忠 ,张学宾;Imitation design of temperature field in coloring hot dip galvanization process[J];Transactions of Nonferrous Metals Society of China;2002年05期

7 ;Observabilities and reach-abilities of nonlinear DEDS and coloring graphs[J];Chinese Science Bulletin;2001年08期

8 余道衡;贾积有;;APPLYING OONN TO SOLVE MAP-COLORING PROBLEM[J];Journal of Electronics(China);1993年01期

9 ;Acyclic Edge Coloring of Planar Graphs without Adjacent Triangles[J];数学研究及应用;2012年04期

10 ;k-fold coloring of planar graphs[J];Science China(Mathematics);2010年10期

相关会议论文 前4条

1 Meirong Xu;Yige Zhao;;A Matrix Approach to List Coloring problems[A];第36届中国控制会议论文集（A）[C];2017年

2 ;[r,s,t]-Coloring of the Joint Graph C_m∨C_n[A];中国自动化学会控制理论专业委员会B卷[C];2011年

3 许晓东;赵文飞;邵泽辉;梁美莲;;集染色顶点Folkman数和集染色边Folkman数(英文)[A];广西计算机学会2014年学术年会论文集[C];2014年

4 ;Decomposition of K_(2n) into n-1 Hamiltonian Cycles and a perfect matching M_i[A];第24届中国控制与决策会议论文集[C];2012年

相关博士学位论文 前1条

1 高毓平;图的边染色及一些有限制条件的染色[D];山东大学;2016年

相关硕士学位论文 前10条

1 邵瑞芳;乘积图的多彩着色[D];天津师范大学;2018年

2 杨芳;几类图的点可区别正常边染色和全染色[D];西北师范大学;2014年

3 马莎莎;笛卡尔乘积图的均匀染色[D];天津师范大学;2016年

4 桂秀平;[D];南京师范大学;2017年

5 张维娟;仙人掌的连续边着色[D];新疆大学;2006年

6 林年锋;平方图的染色[D];南京师范大学;2004年

7 严晓燕;图的2-距离染色[D];浙江师范大学;2014年

8 杨超;关于具有一个或多个可区分约束条件的图着色研究[D];西北师范大学;2014年

9 黄小佳;关于圈的D(d)-点可区别正常全染色的研究[D];西北师范大学;2016年

10 张静雯;最大度为6的平面图的全染色[D];浙江师范大学;2011年

，

本文编号：2636638