边染色超图的划分和覆盖问题研究

《边染色超图的划分和覆盖问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2018届研究生博士学位论文分类号:学校代码:10269密级:学号:52140601022EastChinaNormalUniversity博士学位论文DOCTORALDISSERTATION论文题目：边染色超图的划分和覆盖问题研究院系：数学科学学院专业名称：运筹学与控制论研究方向：图论及其应用指导教师：吕长虹教授学位申请人：王兵2018年5月8日Dissertationfordoctoraldegreein2018StudentID：52140601022Universitycode:10269EastChinaNorm

2、alUniversityTitle:ResearchonPartitionandCoveringofEdge-ColoredHypergraphsDepartment:SchoolofMathematicalSciencesMajor:OperationalResearchandCyberneticsResearchDirection:GraphTheoryanditsApplicationsSupervisor:Prof.ChanghongLuCandidate:BingWangMay8th2018：华东师范大学学位

3、论文原创性声明郑重声明：本人呈交的学位论文《边染色超图的划分和覆盖问题研究》是在华东师范大学攻读硕士博（请勾选）学位期间在导师的指导下进行的研／＃：究工作及取得的研究成果．除文中己经注明引用的内容外．本论文不仅含其他个．对本文的研宄做出重要贡献的个人和集体人己经发表或撰写过的研宄成果．均己在文中作了明确说明并表示谢意．ｚ作者签名：－日期：年ｒ月２日华东师范大学学位论文著作权使用声明《边染色超图的划分和覆盖问题研宄》系本人在华东师范火学攻读学位期间在导师指导下完成的硕士博（请勾选）

4、学位论文／＃：木论文的著作权归本人．本人同意华东师范大学根据相关规定保留和使用此学位论文所有．并向主管部门和学校指定的相关机构送交学位论文的印刷版和电子版位论文进入＾；允许学华东师范大学图书馆及数据库被查阅借阅学位论文加入全国博士、，；同意学校将硕士学位论文共建单位数据库进行检索将学位论文的标题和摘要汇编出版．，采用影印、缩印或者其它方式合理复制学位论文．本学位论文属于（请勾选）＇？＇，“？？１．经华东师范大学相关部门审查核定的或涉密学位论文（）内部．于年月日解密适用上述授权．，解密

5、后Ｖ２．不保密适用上述授权．（），导师签名；：签：该本人名．．，Ｔ１」年：乙１＞》“”＊涉应是己经学定密学位论文华东师范大学位评委ｗ会办公室或保密委“员研会审定过的学位论文需附获批的《华东师范宂生大学中请学位论（文涉”上述）密审批表》方为有效未经文．部门审定的学位论均为公开，学位论文此声明栏不填写的默认为公开学位论文均适用上授权；，述）！博博博士士士学学学位位位论论论文文文答答答辩辩辩委委委员员员会会会成成成员员员名名名单单单姓名职称单位备注张晓东教授上海交通大学主席康丽英教授上海大学单

6、而芳教授上海大学任韩教授华东师范大学詹兴致教授华东师范大学华东师范大学博士学位论文边染色超图的划分和覆盖问题研究摘摘摘要要要图(超图)的划分和覆盖是属于图论的Ramsey理论的一类经典问题.它包含两个子问题:一、在一个任意的r-边染色完全图(超图)中我们一定能够找到最多包含多少个顶点且具有特定结构的单色子图(超图)?二、需要至少多少个特定类型的单色子图(超图)就一定可以覆盖一个任意r-边染色完全图(超图)的所有顶点?该类问题在图的层面结果很多,然而在超图中相应的结果很少,甚至在2-边染色一致完全超图中,基本的路和圈划分和覆

7、盖以及相关的Ramsey数问题也没有得到完全解决.本论文主要研究边染色一致超图的线性路和线性圈划分和覆盖问题.在此基础上研究边染色一致完全超图的ℓ-路和ℓ-圈以及其他子图的划分和覆盖问题.本论文分为以下五个章节.第一章我们介绍了一些基本概念和定义,比较全面地介绍了与本论文相关的边染色图划分和覆盖的已知结果和重要猜想.第二章我们介绍了边染色超图的基本概念,给出了边染色超图划分和覆盖的相关结论.并重点研究了2-边染色k-一致完全超图线性路划分和覆盖问题.这一问题源于2013年Gy´arf´as和S´ark¨ozy提出的如下猜想

8、.猜想:每个2-边染色k-一致完全超图Kk一定存在两条顶点不交且颜色不同的n单色线性路覆盖Kk中至少n−k+2个顶点.nGy´arf´as和S´ark¨ozy说明了如果猜想成立,则该结果对充分大的n是紧的.Gy´arf´as和S´ark¨ozy证明了每个2-边染色k-一致完全超图Kk一定存在两条顶n点不