關于圖的幾類著色問題的研究.pdf

1、圖G的關聯(lián)著色σ為由I(G)到顏色集C的一個映射σ,使得I(G)中任何相鄰的關聯(lián)對都著不同的顏色.若σ:I(G)→C是G的關聯(lián)著色且滿足｜C｜=k,k是一個正整數(shù),則稱σ是G的一個k-關聯(lián)著色,使得G存在k-關聯(lián)著色的最小值k稱為G的關聯(lián)色數(shù),記作Xi(G),即Xi(G)=min{｜C‖σ:I(G)→C是G的關聯(lián)著色}.
　　鄰點可區(qū)別關聯(lián)著色的定義是在關聯(lián)著色的基礎上推廣出來的,進一步細化了圖的著色參數(shù):若對任意uv∈E(G)滿

2、足C(u)≠C(v),則稱σ為G的k-鄰點可區(qū)別關聯(lián)著色,并稱xai(G)=min{｜k｜k是G的k-鄰點可區(qū)別關聯(lián)著色}為G的鄰點可區(qū)別關聯(lián)色數(shù).
　　本文從圖的結構和性質出發(fā),利用反證法和枚舉法研究一些圖的鄰點可區(qū)別關聯(lián)著色,定義了圖的k-d-距離可區(qū)別關聯(lián)著色和點可區(qū)別關聯(lián)著色,并確定了幾類圖的k-d-距離可區(qū)別關聯(lián)色數(shù)和一些圖的點可區(qū)別關聯(lián)色數(shù).
　　本文共分六章,具體安排如下:
　　第二章中,主要給出了圖論的

3、基礎知識和相關引理,并定義了三類新圖.
　　第三章中,主要研究討論了θ-圖、廣義θ-圖和廣義星圖的鄰點可區(qū)別關聯(lián)著色.
　　第四章中,在圖的鄰點可區(qū)別關聯(lián)著色的基礎上定義了圖的k-d-距離可區(qū)別關聯(lián)著色的概念,研究了圖的k-d-距離可區(qū)別關聯(lián)著色的幾條性質和幾類圖的k-d-距離可區(qū)別關聯(lián)著色,確定了星Sn、扇Fn+1(n≥3)、輪Wn+1(n≥4)、圈Cn(n≥4)和向日葵圖的k-2-距離可區(qū)別關聯(lián)色數(shù),以及路Pn(n≥5)