本文主要研究内容
作者王莹（2019）在《图的强边染色和星边染色》一文中研究指出：本文主要研究图的强边染色和星边染色.图G的一个正常k-边染色是指一个映射φ:E(G)→{1,2,...,k},使得对任意两条相邻的边e1,e2都有φ(c1)≠φ(c2).若图G有一个正常k-边染色,那么就称G是k-边可染的.图G的边色数是使G有一个正常k-边染色的最小非负整数k,用χ’(G)表示.若在图G的一个正常k-边染色φ下,任意两条距离至多是2的边染不同的颜色,则称φ是G的一个强k-边染色.若图G有一个强k-边染色,我们称G是强k-边可染的.图G的强边色数是使G是强k-边可染的最小非负整数k,用χ’s(G)来表示.若在图G的一个正常k-边染色φ下,G中不存在长度为4的双色路或双色圈,则称φ是G的一个星k-边染色,即G中任意长度为4的路或圈至少用三种颜色染色.若图G有一个星k-边染色,那么就称G是星k-边可染的.图G的星边色数是使G是星k-边可染的最小非负整数k,用χ’st(G)表示.根据定义,可知χ’s(G)≥χ’st(G)≥χ’(G)≥ △.1983 年,Fouquet 和 Jolivet 提出了强边染色的概念.1989 年,Erdos 和 Nesetril提出猜想:对任意的图G,若△为偶数,则χ’s(G)≤5/4△2;若△为奇数,则χ’s(G)≤5/4△2-1/2△+1/4.目前,当△ ≤ 3时,猜想已经被验证成立;但当△ ≥ 4时,猜想尚未解决.1990年,Faudree等人研究了平面图的强边染色,并证明了对△ ≥ 3的平面图G有χ’s(G)≤ 4χ’(G)≤ 4△+4.同时,他们构造了一类最大度△ ≥ 2且χ’s(G)=4△-4的平面图.2013年,Hocquard等人证明了每个△ ≥ 3的外平面图G满足χ’s(G)≤ 3△一3,并且他们指出这个上界是紧的.Liu和Deng于2008年提出了星边染色的概念.同时,他们证明了对△ ≥ 7的简单图G有χ’st(G)≤[16(△-1)3/2].2016年,Bezegova等人研究了外平面的星边色数并证明:若G是一个外平面图,则有χ’st(G)≤[1.5△]+12.更进一步,他们猜想:对每个△ ≥ 3的外平面图G都有χ’st(G)≤[1.5△]+1.本学位论文主要研究了最大度为4的平面图、外平面图、弦图的强边染色问题,平面图、无K4-子式的图、外平面图、最大度为4的图的星边染色问题,共分成六章.在第一章中,我们给出了本文所涉及的基本概念和相关领域的研究现状,并呈现了本文的主要结果.在第二章中,我们研究了最大度是4的平面图的强边染色,证明了每个△=4的平面图是强19-边可染的,这个结果改进了这类图的强边色数的已知上界20.在第三章中,我们研究了外平面图的强边染色,刻画了 △ ≥ 3且达到强边色数上界3△一3的外平面图,即我们证明了 △ ≥ 3且不含几个特定结构的外平面图G满足X’s(C)≤3△-4.在第四章中,我们研究了弦图的强边染色,证明了对每个弦图G都有χ’s(G)≤△2-2△+3,这说明强边染色猜想对这类图成立.在第五章中,我们研究了若干图的星边染色,尤其是给出了平面图以及一些特殊平面图的星边色数的较好上界,并证明了以下结果:(1)若G是一个平面图,则有χ’st(G)≤ 2.75△+18.(2)若G是一个无K4-子式的图,则有χ;st(G)≤ 2.25△+6.(3)若G是不含4-圈的平面图,则有χ’st(G)≤[1.5△]+18.(4)若G是围长g(G)≥ 5的平面图,则有χ’st(G)≤[1.5△]+13.(5)若G是围长g(G)≥ 8的平面图,则有χ’st(G)≤[1.5△]+3.(6)若G是一个外平面图,则有χ’st(G)≤[1.5△]+5.在第六章中,我们研究了最大度是4的一般图的星边染色,证明了以下两个结果:(1)若G是△=4的图,则有χ’st(G)≤ 14.(2)若G是△=4的二部图,则有χ’st(G)≤ 13.
Abstract
ben wen zhu yao yan jiu tu de jiang bian ran se he xing bian ran se .tu Gde yi ge zheng chang k-bian ran se shi zhi yi ge ying she φ:E(G)→{1,2,...,k},shi de dui ren yi liang tiao xiang lin de bian e1,e2dou you φ(c1)≠φ(c2).re tu Gyou yi ge zheng chang k-bian ran se ,na me jiu chen Gshi k-bian ke ran de .tu Gde bian se shu shi shi Gyou yi ge zheng chang k-bian ran se de zui xiao fei fu zheng shu k,yong χ’(G)biao shi .re zai tu Gde yi ge zheng chang k-bian ran se φxia ,ren yi liang tiao ju li zhi duo shi 2de bian ran bu tong de yan se ,ze chen φshi Gde yi ge jiang k-bian ran se .re tu Gyou yi ge jiang k-bian ran se ,wo men chen Gshi jiang k-bian ke ran de .tu Gde jiang bian se shu shi shi Gshi jiang k-bian ke ran de zui xiao fei fu zheng shu k,yong χ’s(G)lai biao shi .re zai tu Gde yi ge zheng chang k-bian ran se φxia ,Gzhong bu cun zai chang du wei 4de shuang se lu huo shuang se juan ,ze chen φshi Gde yi ge xing k-bian ran se ,ji Gzhong ren yi chang du wei 4de lu huo juan zhi shao yong san chong yan se ran se .re tu Gyou yi ge xing k-bian ran se ,na me jiu chen Gshi xing k-bian ke ran de .tu Gde xing bian se shu shi shi Gshi xing k-bian ke ran de zui xiao fei fu zheng shu k,yong χ’st(G)biao shi .gen ju ding yi ,ke zhi χ’s(G)≥χ’st(G)≥χ’(G)≥ △.1983 nian ,Fouquet he Jolivet di chu le jiang bian ran se de gai nian .1989 nian ,Erdos he Nesetrildi chu cai xiang :dui ren yi de tu G,re △wei ou shu ,ze χ’s(G)≤5/4△2;re △wei ji shu ,ze χ’s(G)≤5/4△2-1/2△+1/4.mu qian ,dang △ ≤ 3shi ,cai xiang yi jing bei yan zheng cheng li ;dan dang △ ≥ 4shi ,cai xiang shang wei jie jue .1990nian ,Faudreedeng ren yan jiu le ping mian tu de jiang bian ran se ,bing zheng ming le dui △ ≥ 3de ping mian tu Gyou χ’s(G)≤ 4χ’(G)≤ 4△+4.tong shi ,ta men gou zao le yi lei zui da du △ ≥ 2ju χ’s(G)=4△-4de ping mian tu .2013nian ,Hocquarddeng ren zheng ming le mei ge △ ≥ 3de wai ping mian tu Gman zu χ’s(G)≤ 3△yi 3,bing ju ta men zhi chu zhe ge shang jie shi jin de .Liuhe Dengyu 2008nian di chu le xing bian ran se de gai nian .tong shi ,ta men zheng ming le dui △ ≥ 7de jian chan tu Gyou χ’st(G)≤[16(△-1)3/2].2016nian ,Bezegovadeng ren yan jiu le wai ping mian de xing bian se shu bing zheng ming :re Gshi yi ge wai ping mian tu ,ze you χ’st(G)≤[1.5△]+12.geng jin yi bu ,ta men cai xiang :dui mei ge △ ≥ 3de wai ping mian tu Gdou you χ’st(G)≤[1.5△]+1.ben xue wei lun wen zhu yao yan jiu le zui da du wei 4de ping mian tu 、wai ping mian tu 、xian tu de jiang bian ran se wen ti ,ping mian tu 、mo K4-zi shi de tu 、wai ping mian tu 、zui da du wei 4de tu de xing bian ran se wen ti ,gong fen cheng liu zhang .zai di yi zhang zhong ,wo men gei chu le ben wen suo she ji de ji ben gai nian he xiang guan ling yu de yan jiu xian zhuang ,bing cheng xian le ben wen de zhu yao jie guo .zai di er zhang zhong ,wo men yan jiu le zui da du shi 4de ping mian tu de jiang bian ran se ,zheng ming le mei ge △=4de ping mian tu shi jiang 19-bian ke ran de ,zhe ge jie guo gai jin le zhe lei tu de jiang bian se shu de yi zhi shang jie 20.zai di san zhang zhong ,wo men yan jiu le wai ping mian tu de jiang bian ran se ,ke hua le △ ≥ 3ju da dao jiang bian se shu shang jie 3△yi 3de wai ping mian tu ,ji wo men zheng ming le △ ≥ 3ju bu han ji ge te ding jie gou de wai ping mian tu Gman zu X’s(C)≤3△-4.zai di si zhang zhong ,wo men yan jiu le xian tu de jiang bian ran se ,zheng ming le dui mei ge xian tu Gdou you χ’s(G)≤△2-2△+3,zhe shui ming jiang bian ran se cai xiang dui zhe lei tu cheng li .zai di wu zhang zhong ,wo men yan jiu le re gan tu de xing bian ran se ,you ji shi gei chu le ping mian tu yi ji yi xie te shu ping mian tu de xing bian se shu de jiao hao shang jie ,bing zheng ming le yi xia jie guo :(1)re Gshi yi ge ping mian tu ,ze you χ’st(G)≤ 2.75△+18.(2)re Gshi yi ge mo K4-zi shi de tu ,ze you χ;st(G)≤ 2.25△+6.(3)re Gshi bu han 4-juan de ping mian tu ,ze you χ’st(G)≤[1.5△]+18.(4)re Gshi wei chang g(G)≥ 5de ping mian tu ,ze you χ’st(G)≤[1.5△]+13.(5)re Gshi wei chang g(G)≥ 8de ping mian tu ,ze you χ’st(G)≤[1.5△]+3.(6)re Gshi yi ge wai ping mian tu ,ze you χ’st(G)≤[1.5△]+5.zai di liu zhang zhong ,wo men yan jiu le zui da du shi 4de yi ban tu de xing bian ran se ,zheng ming le yi xia liang ge jie guo :(1)re Gshi △=4de tu ,ze you χ’st(G)≤ 14.(2)re Gshi △=4de er bu tu ,ze you χ’st(G)≤ 13.
论文参考文献
论文详细介绍
论文作者分别是来自浙江师范大学的王莹，发表于刊物浙江师范大学2019-10-21论文，是一篇关于强边染色论文,星边染色论文,平面图论文,外平面图论文,权转移论文,边分解论文,浙江师范大学2019-10-21论文的文章。本文可供学术参考使用，各位学者可以免费参考阅读下载，文章观点不代表本站观点，资料来自浙江师范大学2019-10-21论文网站，若本站收录的文献无意侵犯了您的著作版权，请联系我们删除。
标签：强边染色论文; 星边染色论文; 平面图论文; 外平面图论文; 权转移论文; 边分解论文; 浙江师范大学2019-10-21论文;