若干平面图的邻和可区别全染色

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

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

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

3、研宄工作做出贡献的其他个人或集体均已在文中以明确方式标明．，本学位论文原创性声明的法律责任由本人承担．学位论文作者签名：／：日期＞〇＜．Ｕ．＞关于学位论文版权使用授权的说明工业大学关于收集：本人完全了解河北，保存用学位论文的规定学校有权，使采用影印数字化或其它手段保存论文，缩印，扫描，学校有权提供本学位论文全；文或者部分内容的阅览服务：学校有权将学位论文的全部或部分内容编入有关数据库进行检索交流学校有权向国家有关部门或者机构送交论文的复印件和电，；子版．（保密的学位

4、论文在解密后适用本授权说明）学位论文作者签名：１乡：Ｌ日期：知导师签名：曰期：．Ｗ錄弈如“，，２屬河北工业大学硕士学位论文摘要一／ＧＵ五Ｇ１２…Ａ图Ｇ的正常Ａ＞全染色是指个映射仓１４：使得（）（）｛，，，｝，＝相邻或者相关联的元素染不同的颜色．令／Ｍ咖＋以）以外如果对五－；ｅＧＡＡ任意边ｍ都有／⑷＃／⑷则称￥是图Ｇ的；邻和可区别全染色；（），，，的最小值称为图Ｇ的邻和可区别全色数记为Ｇ．，；＾（〇关于图的邻和可区别全色数Ｐｉｌｈｉａｋ和Ｗｏｉｎｉ

5、ａｋ提出猜想：对任意简单图，有沾（Ｇ）仝Ａ（Ｇ）＋３．本文主要考虑了若干平面图的邻和可区别全染色，运用著名的组合零点定理及权转移方法得到下面的结论．一结论１设图Ｇ为任Ｈａｌｉｎ图则，＋３＝０ｑ’＾Ａ（Ｇ）＋２ＡＧ＞５．，（）［并且若ＡＧ２６则Ｇ＝ＡＧ＋２当且仅当Ｇ中存在两个相邻的最大度（〇，；＾（〇（）点．一结论２设图Ｇ是个不含Ｋ－５４图子式的图且Ａ（Ｇ〇２，若Ｇ不包含相邻＝＝的最大度点则成ＧＡＧ＋１否则成ＧＡＧ＋２．

6、，，（）（〇（〇（）结论３设图Ｇ是最大度为ＡＧ的平面图则说Ｇ仝ｍａｘＡＧ＋２１４．（），（）｛（），｝＿ＧｘＧ２１０结论４设图Ｇ是无４圈的平面图则说ＳｍａＡ＋．，（）｛（），｝Ｈａｌｉｎ图－关键词：邻和可区别全染色不含私图子式的图平面图组合零点定理Ｉ若干平面图的邻和可区别全染色ＡＢＳＴＲＡＣＴ？？？ＡｒｏｅｒＡ－ｌｌｈＡ：ｔｏｔａｃｏｏｒｉｎｏｆａｒａＧｉｓａｍａ（）：ＶＧＵＥＧ＾１２：ｐｐｇｇｐｐｊ，，，，（）（

7、）｛｝ｓｕｃｈｔｈａｔａｎｙｔｗｏａｄａｃｅｎｔｏｒｉｎｃｉｄｅｎｔｅｌｅｍｅｎｔｓｏｆＧｈａｖｅｄｉｆｆｅｒｅｎｔｃｏｌｏｒｓ．Ｌｅｔｊ／㈦＝ｉｓａ＾－ｎｅｉｈｂｏｒｓｕｍｄｉｓｔｉｎｕｉｓｈｉｎｔｏｔａｌｃｏｌｏｒｉｎＥ０ｇｇｇｇｕｖｅＥＧ（）ｏｆｒａｈＧｉｆｕｖｆｏｒｅａｃｈｅｄｅｕｖＧＥＧａｎｄｔｈｅｓｍａｌｌｅｓｔｖａｌｕｅｋｇｐｆ（）＾ｆ（）ｇ（）＾ｌｌｄｈｈｂｏｄｌｈｂｄｄｂｉｓｃａｅ

8、ｔｅｎｅｉｇｒｓｕｍｉｓｔｉｎｇｕｉｓｈｉｎｇｔｏｔａｃｒｏｍａｔｉｃｎｕｍｅｒｅｎｏｔｅ，ｙｘＵ〇．）Ｆｏｒｎｅｉｇｈｂｏｒｓｕｍｄｉｓｔｉｎｇｕｉｓｈｉｎｇｔｏｔａｌｃｈｒｏｍａｔｉｃｎｕｍｂｅｒ，ＰｉｌｓｎｉａｋａｎｄＷｏｚｎｉａｋｃｏｎｊｅｃｔｕｒｅｄｔｈａｔｆｏｒａｎｙｓｉｍｐｌｅｇｒａｐｈｗｉｔｈｍａｘｉｍｕｍｄｅｇｒｅｅＡＧＧ＜（），Ｘｓ（）ＡＧ＋３．Ｔｈｅ