平面图的强边色数研究

发布时间：2020-08-31 19:15

　　 图G的强边色数,记为χs'(G),是最小的正整数k,使得图G存在满足下述条件的fk-边着色:每一种颜色的所在的边集(色类)构成该图的一个导出匹配.本论文仅考虑简单图.对一个图G,我们用△ = △(G)表示图G的最大度.本硕士论文主要研究平面图的强边色数.我们的研究目标是要证明下述猜想:对任一平面图G,均有χs'(G)≤ △2.针对这一研究目标,我们利用反证法建立了极小反例的若干结构性质,并由此得到使得该猜想成立的若干图类.在结构分析过程中,我们采用的一个重要工具是相异代表系(SDR).本文的研究内容分为两部分.第一部分主要讨论使得猜想不成立的极小反例平面图G的结构性质,其中的极小反例平面图G满足:χs'(G)≥ △2 + 1并且|V(G)| + |E(G)丨尽可能小.第二部分主要研究平面二部图及最大度大于等于8的平面图的强边色数问题.本文的主要结果如下:(1)若图G是平面二部图,则它的强边色数χs'(G)≤ △2,其中△7.(2)若图G是最大度△ ≥ 8的平面图,则它的强边色数χs'(G)≤ △2.(3)极小反例平面图G不存在1度顶点.(4)若图G为极小反例平面图,则对任意的边xy ∈E(G),均有d(x)+d(y)≥ △ + 2.(5)极小反例平面图G不存在3-圈,使得3-圈中包含2-顶点,3-顶点和4-顶点.(6)极小反例平面图G不存在4-圈,使得4-圈中包含2-顶点.(7)极小反例平面图G是2-连通的.
【学位单位】：郑州大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5

【相似文献】

相关期刊论文 前10条

1 李树霞;阿勇嘎;;图的扩容图的色数、边色数[J];内蒙古师范大学学报(自然科学汉文版);2018年05期

2 崔俊峰;;图的点可区别边色数的一个上界[J];首都师范大学学报(自然科学版);2017年01期

3 朱俊俏;卜月华;;星、扇、轮的联图的点可区别均匀边色数[J];浙江师范大学学报(自然科学版);2014年04期

4 王艺桥;舒巧君;;最大度为4的外平面图的无圈边色数[J];浙江师范大学学报(自然科学版);2014年04期

5 马刚;;一些积图的点可区别均匀边色数[J];数学杂志;2014年05期

6 王艳丽;万慧敏;;笛卡尔积图的集合边色数[J];黑龙江大学自然科学学报;2013年04期

7 马刚;马效敏;马少仙;;图M(P_n)和M(C_n)的点可区别均匀边染色[J];数学研究;2012年01期

8 刘利群;王治文;陈祥恩;;D(2)-点可区别正常边色数的一个上界[J];数学的实践与认识;2012年13期

9 刘信生;路伟华;;图的点可区别星边色数的一个上界(英文)[J];华东师范大学学报(自然科学版);2012年05期

10 陈祥恩;高毓平;;合成图的点可区别正常边色数[J];吉林大学学报(理学版);2011年02期

相关会议论文 前3条

1 刘华;赵鹏;马明;冶建华;张忠辅;;图S_m*F_n的邻点可区别的边色数[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

2 包世堂;;关于C_m懔C_n的边色数[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

3 马刚;;S_m∨F_n的全色数和点可区别边色数[A];中国运筹学会第九届学术交流会论文集[C];2008年

相关博士学位论文 前1条

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

相关硕士学位论文 前10条

1 张姗姗;平面图的强边色数研究[D];郑州大学;2018年

2 元麒旋;图的剖分的强边色数研究[D];郑州大学;2018年

3 章文超;图的贪婪博弈边色数和游戏边色数[D];浙江师范大学;2014年

4 毛新叶;图的点可区别边染色的一些结果[D];西北师范大学;2009年

5 刘利群;图的D（2）-点可区别及点可区别正常边染色[D];西北师范大学;2007年

6 郭振香;对具有大围长可平面图强边色数的研究[D];河南大学;2015年

7 田京京;图的D（β）-点可区别边染色及其概率方法[D];西北师范大学;2007年

8 杨玉红;若干图类的星边染色[D];西北师范大学;2009年

9 邓凯;图的星边染色[D];西北师范大学;2007年

10 朱洪国;图的强边染色[D];浙江师范大学;2017年

本文编号：2809217