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

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

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

【學(xué)位級別】：碩士

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



本文編號：4036767