圖的鄰點可區(qū)分的全染色.pdf

1、山東師范大學(xué)碩士學(xué)位論文圖的鄰點可區(qū)分的全染色姓名：王麗偉申請學(xué)位級別：碩士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：孫磊20080410山東師范大學(xué)碩士學(xué)位論文圖的鄰點可區(qū)分的全染色中文摘要染色問題及許多圖理論都是源自四色問題的研究另外染色問題在組合分析和實際生活中有著廣泛的應(yīng)用，是圖論研究中一個很活躍的課題，各類染色問題被相繼提出并加以發(fā)展、應(yīng)用圖G的一個(正常)七染色【1】是將詹種染色分配給G的頂點集V(G)，使得相鄰兩頂點的顏色不同定義色數(shù)為：x

2、(G)=min例圖G有南染色類似的，圖G的一個(正常)七邊染色【1]是將后種染色分配給G的邊集E(G)，使得有公共端點的兩邊的顏色不同邊色數(shù)x7(G)=min糾圖G有七一邊染色】全染色的概念是對點染色和邊染色的推廣，圖的所有元素(頂點和邊)都將染色且任相鄰或關(guān)聯(lián)的元素染色不同全染色是圖論染色的一個傳統(tǒng)問題，由V江ing(1964)【23】和Behzad(1965)【2425】各自獨立提出的，同時分別給出全染色猜想點可區(qū)分全染色和鄰點可區(qū)

3、分全染色是染色問題的新生點，近來由張忠輔老師提出并給出了相應(yīng)的兩個猜想定義【2】設(shè)G(KE)為圖，良為正整數(shù)，s為七色集，令映射，：y(G)JE(G)一S如果(1)對任意ut，”“∈E(G)u≠叫有，(u“)≠，(u“)；(2)對任意utI∈E(G)，有，(亂)≠，(t，)，，(u)≠，(亂”)，，(札t，)≠廠(口)，那么稱廠為圖G的一個后全染色若還滿足(3)對任意牡：可∈y(G)，c(u)≠c(t，)，其中c(t‘)=，(亂)u，(