图的邻点可区别边色数和全色数

发布时间：2025-03-19 05:53

　　图的染色问题是图论的一个重要分支,它起源于著名的“四色问题”.图的染色理论已广泛应用于计算机科学、无线网络等领域.设NG(v)和NG(u)表示图G的中顶点v和u的邻点所构成的集合.图G的k-邻点可区别边染色是G的一个正常k-边染色φ,使得对于任意边uv∈E(G)都有Cφ(u)≠Cφ(v),其中Cφ(v)={φ(vx)|x∈NG(v)}且Cφ(u)={φ(uy)|y ∈NG(u)}.并称使得图G有一个k-邻点可区别边染色的最小正整数k为图G的邻点可区别边色数(以下简称为NDE-色数),记为χ(G).2002年,Zhang等人首先研究了图的邻点可区别边染色,并提出了猜想:设G是阶至少为3的连通图,且G≠C5,有χa'(G)≤△(G)+2.图G的k-邻点可区别全染色是G的一个正常k-全染色ψ,使得对于任意边 vu ∈ E(G)都有Cψ(v)≠Cψ(u),其中Cψ(v)={ψ(v)}∪{ψ(vx)|x∈NG(v)}且Cψ(u)={ψ(u)}∪{ψ(uy)}|y∈NG(u)}.并称使得图G有一个k-邻点可区别全染色的最小正整数k为图G的邻点可区别全色数(以下简称为AVDT-色数),记为χa"(G)...

【文章页数】：81 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 基本概念与符号
        1.1.1 图的定义
        1.1.2 平面图
        1.1.3 权转移方法
    1.2 两种染色的研究进展
        1.2.1 图的邻点可区别边染色
        1.2.2 图的邻点可区别全染色
    1.3 本文的主要结果
第二章 平面图的邻点可区别边染色
    2.1 预备引理
    2.2 权转移
第三章 平面图的邻点可区别全染色
    3.1 最大度为12的平面图
        3.1.1 预备知识
        3.1.2 结构分析
        3.1.3 权转移
    3.2 最大度为11的平面图
        3.2.1 可约子图
        3.2.2 主要结论的证明
参考文献
攻读学位期间取得的研究成果
致谢



本文编号：4036767