關(guān)于幾類圖的著色強(qiáng)度研究.pdf

1、圖G的最優(yōu)著色是從頂點(diǎn)集V到顏色集C的一個(gè)映射f:V→C,使得G中任意兩個(gè)相鄰的頂點(diǎn)均有不同的象,而且∑f(v)取得最小值,稱min∑f(v)為G的最小頂點(diǎn)著色和(MVCS),記為∑(G),即∑(G)=min∑f(v).如果f是G的一最優(yōu)著色,則將f所需要的最小顏色數(shù)稱為G的頂點(diǎn)強(qiáng)度,記為s(G).對(duì)于一般的圖類,s(G)不小于x(G).
　　圖G的最優(yōu)邊著色是從邊集E到顏色集C的一個(gè)映射f:E→C,使得G中任意兩個(gè)相鄰的邊均有不

2、同的象,而且∑f(e)取得最小值,稱min∑f(e)為G的最小邊著色和(MECS),記為Σ′(G),即Σ′(G)=min∑f(e).如果f是G的一最優(yōu)邊著色,則將f所需要最小顏色數(shù)稱為G的邊強(qiáng)度,記為s′(G).
　　本文第二章研究了θ-圖的頂點(diǎn)著色和頂點(diǎn)強(qiáng)度的)∑(G)與s(G)以及邊著色和邊強(qiáng)度的Σ′(G)與s′(G).
　　目前關(guān)于Σ'(G)與s'(G)的研究已經(jīng)很充分.在此文章中,在圖的全著色的基礎(chǔ)上,我們將對(duì)以上兩

3、個(gè)概念加以推廣,本文在第三章中給出了圖的最優(yōu)頂點(diǎn)著色和頂點(diǎn)強(qiáng)度.對(duì)圖G=(V,E)的映射f:{V,E}→{1,2,…,k},若滿足如下條件:▽u,v,w∈V,uv,vw∈E且u≠v≠w，有f(u)≠f(v)≠f(w)；則稱f為G的一個(gè)l=2的頂點(diǎn)著色,簡(jiǎn)記為l2-VC of G
　　.稱∑(G)=min∑f(v)為G的間隔度為l=2的最小著色和,將f所需要的最小顏色數(shù)稱為G的強(qiáng)度,記為sT(G).
　　在第四章中,利用窮染法