圖的sigma邊染色研究.pdf

1、近年來,很多學(xué)者致力于研究圖的頂點(diǎn)和邊的識(shí)別與區(qū)分,他們使用的很多方法都涉及了圖的染色,如邊可區(qū)分頂點(diǎn)染色、頂點(diǎn)可區(qū)分邊染色i邊權(quán)值頂點(diǎn)染色等.上述染色均可稱為鄰居可區(qū)分染色,所謂鄰居可區(qū)分染色即指c是圖G的頂點(diǎn)染色或邊染色,對(duì)于任意的兩個(gè)相鄰的元素,與其中一個(gè)元素相關(guān)聯(lián)的元素的顏色類和與另一個(gè)元素相關(guān)聯(lián)的元素的顏色類不同.在這些鄰居可區(qū)分染色的基礎(chǔ)上,Chartrand等人提出了sigma染色的概念,并得到了較完善的結(jié)果.
　　

2、 本文著重研究圖的sigma邊染色問題,主要工作有:
　　 (1)提出了圖的sigma邊染色概念,研究了圖的sigma邊染色數(shù)和邊染色數(shù),圖的sigma邊染色數(shù)和邊數(shù)之間的關(guān)系:
　　 ①sigma邊染色數(shù)與邊染色數(shù)的關(guān)系:首先證明了對(duì)任意連通圖G,有σ'(G)≤x'(G).然后證明了對(duì)任意正整數(shù)a和b,若a≤6,則存在圖G,使得σ'(G)=a,x'(G)=6.
　　 ②sigma邊染色數(shù)與邊數(shù)的關(guān)系:首先證明

3、了G是邊數(shù)為ε的非平凡連通圖,則對(duì)于G的任意sigma邊染色而言,σ'(G)≠ε-1.然后證明了若k,ε是任意正整數(shù),則當(dāng)k≤ε≤2k時(shí),存在邊數(shù)為ε的連通圖G的sigma邊染色數(shù)σ'(G)=k當(dāng)且僅當(dāng)k≠ε-1.
　　 (2)提出了圖的sigma邊連續(xù)的概念.根據(jù)邊染色數(shù)與sigma邊染色數(shù)之間的關(guān)系給出了路、圈和星圖的sigma邊染色數(shù),然后利用構(gòu)造染色方案的方法證明了路、圈和星圖是sigma邊連續(xù)的.
　　 (3)