若干图的邻和可区别边染色

《若干图的邻和可区别边染色》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：密级：ＵＤＣ２０１４２１１０５００１：编号：河北工业大学硕士学位论文若干图的邻和可区别边染色论文作者：潘文华学生类别：全日制学科门类：理学硕士学科专业：运筹学与控制论指导教师：徐常青职称：教授资助基金项目：必要时填写（）ＤｉｓｓｅｒｔａｔｉｏｎＳｕｂｍｉｔｔｅｄｔｏＨｅｂｅｉＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙｆｏｒＴｈｅＭａｓｔｅｒＤｅｒｅｅｏｆｇＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈａｎｄＣｙｂｅｒｎｅ

2、ｔｉｃｓＮＥＩＧＨＢＯＲＳＵＭＤＩＳＴＩＮＧＵＩＳＨＩＮＧＥＤＧＥＣＯＬＯＲＩＮＧＯＦＳＯＭＥＧＲＡＰＨＳｂｙＰａｎＷｅｎｈｕａＳｕｐｅｒｖｉｓｏｒ：Ｐｒｏｆ．ＸｕＣｈａｎｇｑｉｎｇＤｅｃ．２０１６原创性声明本人郑重声明：所呈交的学位论文是本人在导师指导下，进行研宄工作所，取得的成果．除文中已经注明引用的内容外本学位论文不包含任何他人或集体，已经发表的作品内容也不包含本人为获得其他学位而使用过的材料．对本论文，所涉及的研宄工作做出贡献的其他个人或集体均已在

3、文中以明确方式标明．本，学位论文原创性声明的法律责任由本人承担．免年．Ｚ：ｌＯ学位论文作者签名：日期Ｚｏ＆Ｕ关于学位论文版权使用授权的说明本人完全了解河北工业大学关于收集：学校有权，保存，使用学位论文的规定采用影印，缩印，扫描，数字化或其它手段保存论文；学校有权提供本学位论文全文或者部分内容的阅览服务：学校有权将学位论文的全部或部分内容编入有关数据库进行检索交流学校有权向国家有关部门或者机构送交论文的复印件和电，；子版．（保密的学位论文在解密后适用本授权说明）５金之兮：．学位论文

4、作者签名：日期如义｜１如导师签名：曰期：。錄奉Ｉ２以，如河北工业大学硕士学位论文摘要一一五Ｇ１２…Ａ图Ｇ的个正常Ａ＞边染色是个映射４；满足每０（）｛，，，｝，对相邻的边染不同的颜色．记／〃是与点〃相关联的边的颜色的和．若对Ｇ的（）每条边都有／⑷ｆ／⑷则称４是图Ｇ的Ａ＞邻和可区别边染色．图Ｇ存在，＇Ａ＞记作．邻和可区别边染色的Ａ：的最小值称为图Ｇ的邻和可区别边色数Ｇ，Ｘｓ（〇用ＡＧ和ｍａｄＧ分别表示图Ｇ的最大度和最大平均度．２０１１年Ｆｌａｎｄｒｉｎ等（〇（〇，人提出图的邻和可

5、区别边染色猜想：如果连通图Ｇ至少含３个顶点且ＧｆＣ５，则ＧＡＧ＋２．Ｋ（）Ｓ（）本文运用组合零点定理和权转移方法研究了不含孤立边的无私－图子式的一图５：、类稀疏图及围长大于等于的平面图的邻和可区别边染色得到如下结论，－图Ｇ是不含孤立边的无Ｋ４图子式的图且ＡＧ２６．若Ｇ不含相⑴设（）＇＇邻最大度点则Ｇ＝ＡＧ否则Ｇ＝ＡＧ＋１．，Ｘｓ（〇（〇，ｘｓ（〇（〇图Ｇ不含孤立边ＡＧ２６且ｍａｄＧ．若Ｇ不含相邻最大度⑵设，（〇（）仝｜＇＇＝＝点则ＧＡＧ否则ＧＡＧ＋１．

6、，ＸＳ（）（），ＸＳ（）（）＇３若图Ｇ是不含孤立边的围长大于等于５的平面图则ＸＧｍａｘ（），Ｓ（）仝ＡＧ＋２９．（（），｝结论⑴和结论⑵分别确定了不含孤立边且ＡＧ２６的无私－图子式（）的图ｆ和ｍａｄＧＳ的图的邻和可区别边色数结论３证明了邻和可区别边（）ｆ；（）染色猜想对ＡＧ２７且围长大于等于５的平面图成立．（）关键词－：邻和可区别边染色无Ｋ４图子式的图稀疏图平面图组合零点定理Ｉ若干图的邻和可区别边染色ＡＢＳＴＲＡＣＴ？？？ＡｒｏｅｒＡ－ｄｌｈＥＡ

7、：ｅｅｃｏｏｒｉｎｏｆａｒａＧｉｓａｍａｉｎ（）：Ｇ＾１２：ｐｐｇｇ０ｇｐｐｐｇｊ，，，｛）｛｝ｓｕｃｈｔｈａｔｅａｃｈａｄａｃｅｎｔｅｄｇｅｓｒｅｃｅｉｖｅｄｉｆｆｅｒｅｎｔｃｏｌｏｒｓ．Ｌｅｔｆｖｂｅｔｈｅｓｕｍｏｆｊ｛）ｌｔｈｅｅｄｉｉｄｔｗｉｔｈ－ｃｏｏｒｓｏｎｇｅｓｎｃｅｎｖ．（）ｉｓｃａｌｌｅｄａ＾ｎｅｉｈｂｏｒｓｕｍｄｉｓｔｉｎｕｉｓｈｉｎｊｇｇｇｅｄｇｅｃｏｌｏｒｉｎｇｉｆｆ｛ｕ）？ｆ（ｖ）ｆｏｒ

8、ｅａｃｈｅｄｇｅｕｖＧＥ｛Ｇ）．ＴｈｅｓｍａｌｌｅｓｔｋｓｕｃｈｔｈａｔＧｈａｓａ＾－ｎｅｉｇｈｂｏｒｓｕｍｄｉｓｔｉｎｇｕｉｓｈｉｎｇｅｄｇｅｃｏｌｏｒｉｎｇｉｓｃａｌｌｅｄｔｈｅｎｅｉｇｈｂｏｒｄ’ｓｕｍｉｓｔｉｎｇｕｉｓｈｉｎｇｉｎｄｅｘｄｅｎｏ