發(fā)布時間：2025-03-19 05:53

　　圖的染色問題是圖論的一個重要分支,它起源于著名的“四色問題”.圖的染色理論已廣泛應用于計算機科學、無線網絡等領域.設NG(v)和NG(u)表示圖G的中頂點v和u的鄰點所構成的集合.圖G的k-鄰點可區(qū)別邊染色是G的一個正常k-邊染色φ,使得對于任意邊uv∈E(G)都有Cφ(u)≠Cφ(v),其中Cφ(v)={φ(vx)|x∈NG(v)}且Cφ(u)={φ(uy)|y ∈NG(u)}.并稱使得圖G有一個k-鄰點可區(qū)別邊染色的最小正整數(shù)k為圖G的鄰點可區(qū)別邊色數(shù)(以下簡稱為NDE-色數(shù)),記為χ(G).2002年,Zhang等人首先研究了圖的鄰點可區(qū)別邊染色,并提出了猜想:設G是階至少為3的連通圖,且G≠C5,有χa'(G)≤△(G)+2.圖G的k-鄰點可區(qū)別全染色是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-鄰點可區(qū)別全染色的最小正整數(shù)k為圖G的鄰點可區(qū)別全色數(shù)(以下簡稱為AVDT-色數(shù)),記為χa"(G)...

【文章頁數(shù)】：81 頁

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 基本概念與符號
        1.1.1 圖的定義
        1.1.2 平面圖
        1.1.3 權轉移方法
    1.2 兩種染色的研究進展
        1.2.1 圖的鄰點可區(qū)別邊染色
        1.2.2 圖的鄰點可區(qū)別全染色
    1.3 本文的主要結果
第二章 平面圖的鄰點可區(qū)別邊染色
    2.1 預備引理
    2.2 權轉移
第三章 平面圖的鄰點可區(qū)別全染色
    3.1 最大度為12的平面圖
        3.1.1 預備知識
        3.1.2 結構分析
        3.1.3 權轉移
    3.2 最大度為11的平面圖
        3.2.1 可約子圖
        3.2.2 主要結論的證明
參考文獻
攻讀學位期間取得的研究成果
致謝



本文編號：4036767