The Star Edge Coloring of Some Subcubic Graphs

发布时间：2021-11-19 13:21

　　图染色问题是图论的重要研究专题之一.若图G的正常顶点染色不出现长为3的双色路,称这种染色为图G的星染色.使得图G的星染色数最小的颜色数叫做星色数,用χst（G）表示.2008年,刘信生和邓凯首次在星染色的基础上给出了星边染色的概念.若图G的正常边染色满足不出现2-边染色的4长路和4长圈,这种染色称为图G的星边染色.使得图G的星边染色颜色数最小的色数叫做星边色数,记为χst’（G）.Fouquet和Jolivet在1983年提出强边染色的概念以解决涉及无线电网络及其频率分配的问题.若图G的正常边染色使得没有一条边可以与两个颜色相同的边相邻,而每个色类都导出图G的一个匹配,那么这种染色称作图G的强边染色,使得图G的强边染色最小的色数叫做强边色数,记为χs’（G）.由于给定图的星边色数与其强边色数,列表星边色数,无圈边染色数有一定的联系,例如给定图的星边色数小于等于它的强边色数等,所以我们研究图的星边色数对强边色数,列表星边色数和无圈边染色数具有一定的意义.在文中我们进一步对次三正则图的星边染色进行研究,主要研究了广义Petersen图和Sierpinski图的星边色数并分别给出了一种可行的... 

【文章来源】：天津师范大学天津市

【文章页数】：41 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
Chapter 1 Introduction
    1.1 Prelimiaries
    1.2 Studing Background
        1.2.1 The exact value of star chromatic index of some graphs
        1.2.2 The bond of star chromatic index of some graphs
        1.2.3 The result of star chromatic index of generalized Petersen graphs
Chapter 2 The star edge coloring of generalized Petersen graphs
    2.1 The star chromatic index of P(n,1)
    2.2 The star chromatic index of P(n,2)
    2.3 The star chromatic index of P(n,3)
Chapter 3 A note on the star chromatic index of subcubic graphs
    3.1 The star edge coloring of Sierpinski graphs S(n,3)
    3.2 The star edge coloring of cubic graphs with star chromatic index 6
Conclusion
References
致谢
攻读学位期间发表的学术论文


【参考文献】：
期刊论文
[1]Embedding Generalized Petersen Graph in Books[J]. Bin ZHAO,Wei XIONG,Yingzhi TIAN,Jixiang MENG.  Chinese Annals of Mathematics（Series B）. 2016(03)
[2]d-维网格的星边染色[J]. 邓凯,刘信生,田双亮.  华东师范大学学报(自然科学版). 2012(03)
[3]极大外平面图的星边染色[J]. 邓凯,田双亮.  高校应用数学学报A辑. 2011(04)
[4]树的星边染色[J]. 邓凯,刘信生,田双亮.  山东大学学报(理学版). 2011(08)



本文编号：3505127