Mycielski图的染色问题 毕业论文.doc

mycielski图的染色问题目 录中文摘要-2英文摘要-3引言-4一、mycielski图的定义-51 mycielski图的定义-52 . 广义mycielski图的定义-5二、mycielski图的染色问题-5(一)边色数-51. mycielski图的边色数-5 2.广义myc ielski 图的边色数-6(二)邻强边色数-61. myciel ski 图的邻强边色数-72. 广义mycielski 图的邻强边色数-7（三）全色数-8 1. mycielski图的全色数-82. 广义mycielski图的全色数-9（四）邻点可区别全色数-91.mycielski 图的邻点可区别全色数-102.广义mycielski图的邻点可区别全色数-12致谢-13参考文献-14摘要：本论文总结了mycielski 图及广义mycielski 图关于染色问题的各方面定义和定理，主要包括边色数、邻强边色数、全色数、邻点可区别全色数的相关结论。关键词：mycielski 图 ；广义mycielski 图 ；边色数 ；邻强边色数 ；全色数 ； 邻点可区别全色数coloration problems of mycielski graphabstract: the major point of this paper is summarization about the theorem and definition in mycielski graph and general mycielski graph coloration. it has mainly the following aspects: mycielski graph、general mycielski graph、 adjacent e ch romatic number 、adjacent strong edge ch romatic number、to tal ch romat ic number and the adjacent vertex distinguishing total ch romatic number.key words：mycielski graph；general mycielski graph； adjacent e ch romatic number ；adjacent strong edge ch romatic number； to tal ch romat ic number；the adjacent vertex distinguishing total ch romatic number引言 图的染色问题是图论研究的经典领域,在网络问题、组合分析和实际生活中有着广泛的应用,是图论的主要研究内容之一。染色问题源于著名的四色问题。所谓四色猜想就是在平面上任何一张地图，总可以用至多四种颜色给每一个国家染色，使得任何相邻国家的颜色是不同的。四色问题可以转化为图论中的问题来讨论，从地图出发构造一个图g，让每一个顶点代表地图的一个区域，如果两个区域有一段公共边界线，就在相应的顶点之间连上一条边，则对地图的染色就转化为对图g的一个顶点染色。本论文总结了mycielski 图及广义mycielski 图关于染色问题的各方面定义和定理，主要包括边色数、邻强边色数、全色数、邻点可区别全色数的相关结论。一、mycielski 图的定义1.mycielski 图的定义定义1 对图,记 ,且其中，.称为g的mycielski 图.2.广义mycielski 图的定义定义2 对简单图, = 被称为的广义mycielski 图，若 ,.二、 mycielski 图的染色问题(一) 边色数定义3 对,映射满足若相邻,有,则称为的- 正常边染色,简记作;而ec of 称为的边色数. 1.mycielski 图的边色数定理1 设是简单图,当时,有 其中表示的最大度.定理2 若的最大度点不相邻且,则 猜想 对简单图,当且仅当.其中表示阶为2的完全图.2.广义mycielski 图的边色数定理1 对个点的路 定理2 对圈,当时有 .定理3 对阶的轮图,有 定理4 对个点的星图,则有 .定理5 对阶的扇,有 定理6 完全二部图的广义mycielski 图记为.对图,有猜想 对简单图及,其中表示的最大度.(二) 邻强边色数 定义4 对图,若一正常染色满足,其中,则称为的邻强边染色法,简记作,且称 of 为的邻强边色数.1. mycielski 图的邻强边色数定理1 对个点的路, 定理2 对圈,有 定理3 对阶的轮图,有 定理4 设为阶不小于的星图(即完全二部图),则有 定理5 对扇,有 定理6 对完全图,有 2.广义 mycielski 图的邻强边色数定理1 对阶的轮图，有 定理2 完全二部图的广义mycielski 图记为. 对图,有 (三) 全色数定义5 设为简单图,映射: 满足 ; ; 则称为的全染色,简记为tc,并称 tc of 为的全色数1. mycielski 图的全色数定理1 对个点的路, 定理2 对圈,有 定理3 对阶的轮图有 定理4 设为阶不小于的星图（即完全二部图），则有 定理5 对扇，有 定理6 对完全图，有 2. 广义mycielski 图的全色数定理1 对完全二部图的广义mycielski 图,有 .定理2 设是一个阶的圈,则 .(四)邻点可区别全色数定义6 对图,如果的一个正常全染色满足: ,有,其中 ,则称为的一个邻点可区别全染色,简记为avdtc.并称 avdtc 为的邻点可区别全色数.1. mycielski 图的邻点可区别全色数定理1 对阶完全图, .定理2对个点的路,有 定理3 对有个点的圈,有 定理4 对完全图,我们有 .定理5 对完全二部图,我们有 定理6 设是一个个点的星图,则有 .定理7 设是一个有个点的扇,有 定理8 设是一个有个点的轮,则有 .2.广义mycielski 图的邻点可区别全色数定理1 对完全二部图，有 定理2 设是阶圈，则 定理3 对阶星，有 .定理4 设是阶扇, ,则 .定理5 设是阶轮图，则 .参考文献1陈义. 轮图的广义mycielski图的邻强边色数j. 经济数学, 2003, 20 (2) : 7780.2张忠辅,李敬文,邓桂星.关于图的mycielski图的边色数j. 兰州铁道学院学报( 自然科学版). 2003,vol. 22 no. 3.3李敬文,邓桂星.若干图的mycielski图的邻强边色数j. 兰州铁道学院学报( 自然科学版).2003,vol. 22 no. 3. 4 李沐春,强会英,晁福刚,张忠辅. 完全二部图广义mycielski图的邻点可区别全色数与邻强边色数j. 经济数学,2003, vo l138no119.5李敬文,马生全,张忠辅,王文康,马明. 若干图的广义mycielski图的边色数j.兰州交通大学信息与电气工程学院. 经济数学, 2005, vo l135no111.6 张忠辅,李敬文. 若干图的mycielski图的全染色j. 兰州铁道学院学报( 自然科学版). 2003, vol. 22no. 4.7 qian g huiying, zhan g zhongfu. vertex2edge adjacent vertex2distinguishing total coloring of some graphs. school of mat hematics ,physics and software engineering ,lanzhou jiaotong university ,lanzhou . j . of mat h. ( prc).2006, vol . 26 no. 6.8王治文,徐保根,闫丽宏,张忠辅. 关于图的广义mycielski图的全染色j. 山西大学学报(自然科学版). 2008, 31 (4) : 486 488.9强会英,晁福刚,张忠辅. 完全图的广义mycielski图的邻点可区别的全色数j. 兰州交通大学应用数学研究所. 兰州大学学报自然科学