發(fā)布時間：2018-04-03 00:13

  本文選題：平面圖　切入點：鄰和可區(qū)別全染色　出處：《中國礦業(yè)大學》2017年碩士論文

【摘要】：令G = (V(G),E(G))是一個圖,k是一個正整數(shù). G的一個k-全染色是一個映射φ: V(G) ∪ E(G)→{1,2,..., k},且同時滿足以下三個條件:(1).對G中任意一對相鄰的頂點u,v,φ(u)≠φ(v);(2).對G中任意一對相鄰的邊e, e',φ(e)≠φ(e');(3).對G中任意的頂點v,和與v關聯(lián)的邊e,φ(u)≠φ(e).令f(v)表示與頂點v關聯(lián)的所有邊的顏色加上頂點v的顏色的和.圖G的一個k-全染色,如果同時滿足對G中任意的一條邊uv,都有f(u)≠f(v),則稱為G的k-鄰和可區(qū)別全染色,滿足這些染色條件的最小的k-值稱為G的鄰和可區(qū)別全色數(shù),記為χtnsd"(G).給G的每一個頂點和邊z ∈ V∪E都分配一個顏色列表Lz,如果對每一個z∈ V∪E,都可以從其對應的列表Lz中選擇一種顏色對其進行染色,使得G中存在一個鄰和可區(qū)別全染色,則稱G是鄰和可區(qū)別L-列表全可染的,如果對G中的每一個列表L = {Lz||Lz≥ k,z ∈ V∪E}, G都是鄰和可區(qū)別L-列表全可染的,則稱最小的k-值為G的鄰和可區(qū)別全可選擇數(shù),記為chtnsd"(G).關于圖的鄰和可區(qū)別全染色,Pil'sniak和Wo'zniak提出如下猜想:對任意的簡單圖G,χtnsd"(G)≤△(G)+3.這個猜想已經(jīng)被證明了對于完全圖,圈,二分圖和子立方圖都成立.同時通過比較定義可得:χtnsd"(G)≤chtnsd"(G),因此很多文章開始研究對任意的平面圖χtnsd"(G)≤△(G)+3.是否也成立.本文主要利用反證法,組合零點定理,權轉(zhuǎn)移方法證明了關于平面圖的鄰和可區(qū)別全染色和鄰和可區(qū)別列表全染色的兩個結(jié)論,文章一共分為4章.第1章主要介紹本文的研究背景,相關符號和定義,鄰和可區(qū)別全染色和鄰和可區(qū)別列表全染色及其他相關染色的研究現(xiàn)狀.第2章通過分析不含4-圈且△ ≥ 9的平面圖的結(jié)構,證明了:對于△ ≥ 9且不含4-圈的平面圖,χtnsd"(G) ≤ △(G) + 2.第3章通過分析不含帶弦5-圈且△ ≥ 8的平面圖的結(jié)構,證明了:對于△ ≥8且不含帶弦5-圈的平面圖,chtnsd"(G)≤△(G)+3.根據(jù)χtnsd"(G)≤chtnsd"(G),因此第三章得到的結(jié)論對于鄰和可區(qū)別全染色同樣成立.第4章總結(jié)和展望.
[Abstract]:Let G = G = a graph K is a positive integer.A k-total coloring of G is a mapping 蠁: v _ (G) Karabakh E _ (G) {1 ~ (2) ~ (2) ~ (...., k}), and satisfies the following three conditions: (1) ~ (1) ~ (-1) at the same time.For any pair of adjacent vertices in G, u, 蠁 v) 鈮，

本文編號：1702750