边染色图中的极值问题

发布时间：2023-10-08 18:34

　　本文中,我们主要研究了边染色图中的子图相关的问题。给定一个图G=(V,E)和G上的一个边染色φ:E→{1,2,...,k}。我们称G的一个子图H是正常染色的,如果对任意H中的两条相邻的边e,e’有φ(e)≠φ(e’)。称H是彩色的如果对任意H中的两条不同的边e,e’都有φ(e)≠φ(e’)。H是强边染色的,如果任意H中的长度不超过3的路都是彩色的。称G的子图M是一个匹配,如果M中的边是两两不相交的。我们首先证明了若强边染色图G满足|G|≥2δ(G)+1,则G中包含大小为δ(G)的彩色匹配。此结果部分验证了 Wang,Yan和Yu的一个猜想。其次我们证明了若强边染色图G满足δ(G)>2|G|/3,则G中包含一个彩色哈密顿圈。这可以被视作是强边染色图中的Dirac定理,我们进一步提出了一个相关的猜测。关于一般的边染色图,令色度dc(v)为点v的邻边使用的颜色的个数,以及δc(G)为G中点的最小色度。我们研究了其中的正常染色生成树,并证明了若边染色图G满足δc(G)≥|G|/2,则G中包含一个正常染色生成树,并且这里的下界是紧的。Ron Aharoni最近猜想若图G1,...,Gn是定...

【文章页数】：50 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第一章 绪论
    1.1 基本概念
    1.2 边染色图的极值问题
        1.2.1 匹配,圈与树
        1.2.2 匹配问题的染色版本
        1.2.3 圈问题的染色版本
        1.2.4 边染色图中的生成树
    1.3 吸收技术
    1.4 主要结果
第二章 强边染色图中的彩色匹配和彩色哈密顿圈
    2.1 强边染色图中的彩色匹配
    2.2 强边染色图中的彩色哈密顿圈
第三章 边染色图中的正常染色生成树
    3.1 色度条件下的彩色生成树
    3.2 色度条件下的正常染色生成树
    3.3 边染色完全二部图中的彩色匹配
第四章 图系统中的彩色哈密顿圈
    4.1 基础和定义
    4.2 定理4.0.4的证明
    4.3 定理4.0.5的证明
第五章 总结与展望
    5.1 总结与展望
参考文献
致谢
硕士期间发表的论文
硕士期间获得的奖励
学位论文评阅及答辩情况表



本文编号：3852566