图的点不交的圈和非正常DP-染色

发布时间：2024-06-29 13:07

　　图论是组合的一个重要分支,起源于古老的民间数学游戏,其中最具代表性的有欧拉的哥尼斯堡七桥问题和哈密顿的环游世界游戏.著名的四色问题为图论的形成和发展注入活力.因此,圈问题和染色问题是图论中两个重要而经典的问题.本论文主要研究图与有向图中存在kk个点不交的圈的度条件,其中k是任意正整数,以及稀疏多重图中的非正常DP-染色.我们用G和D分别表示图和有向图.给定图G,用δ(G)、Δ(G)以及dG(x)分别表示图G的最小度、最大度以及点x∈V(G)在G中的度.令σt(G)表示图G中所有t-独立集中点的最小度和,即█为大小为t的独立集},其中t≥2是一个整数.在图和有向图中,把长度为q的圈称为q-圈;当q=|V(G)|时称为哈密顿圈;当q=3时称为三角形.关于圈问题,最经典的结果是Dirac定理:设G是一个n-阶图,其中n≥3.若δ(G)≥n/2,则图G包含一条哈密顿圈.此后,关于圈问题人们展开广泛的研究.我们主要研究存在kk个点不交的圈的度条件.在1963年,Corradi和Hajnal证明了存在k个点不交的圈的最小度条件.Justesen将Corradi-Hajnal定理中的最小度条件推广到...

【文章页数】：128 页

【学位级别】：博士

【文章目录】：
中文摘要
Abstract
第一章 绪论
    1.1 基本术语与符号
    1.2 图与有向图中点不交的圈
    1.3 稀疏图中的非正常染色
    1.4 主要结果
第二章 无向图中点不交的圈
    2.1 重要引理
    2.2 定理证明
第三章 有向图中点不交的圈
    3.1 半度条件下点不交的圈
        3.1.1 主要引理
        3.1.2 定理1.4.2和定理1.4.3的证明
    3.2 出度条件下点不交的圈
        3.2.1 竞赛图中的圈和路
        3.2.2 定理3.2.2的证明
        3.2.3 定理3.2.3的证明
第四章 稀疏多重图中的非正常DP-染色
    4.1 定理1.4.5中下界的证明
        4.1.1 (i,i)-非正常DP-染色
i+1时的(i,j)-非正常DP-染色">        4.1.2 当j>i+1时的(i,j)-非正常DP-染色
        4.1.3 (i,i+1)-非正常DP-染色
    4.2 临界图的构造
第五章 可进一步研究的问题
符号说明
参考文献
致谢
作者简介
攻读博士学位期间完成论文情况
学位论文评阅及答辩情况表



本文编号：3997600