關(guān)于(-)l圖的第二類鄰點可區(qū)別全染色的一些結(jié)果.pdf

1、圖的染色問題是圖論研究中的一個熱點話題.早在1965年M.Behzad就提出了全染色的概念,全染色是指對圖G的頂點和邊同時進行染色,使得任意相鄰或相關(guān)聯(lián)的元素(頂點和邊)均染有不同的顏色,全染色所用的最少的顏色數(shù)就是圖G的全色數(shù).張忠輔等人在全染色的基礎(chǔ)上,提出了鄰點可區(qū)別全染色和鄰點強可區(qū)別全染色的概念.而在本文中,提出了一種新的染色概念,稱為第二類鄰點可區(qū)別全染色.本文共有四章內(nèi)容,主要研究了θk-圖的第二類鄰點可區(qū)別全染色數(shù).

2、r>　　 第一章給出了文中用到的相關(guān)符號,基本概念,相關(guān)結(jié)論以及給出了第二類鄰點可區(qū)別全染色的概念.其內(nèi)容為:
　　 設(shè)圖G=(V,E)是一個階至少為3的連通簡單圖,k是一個正整數(shù),f是V(G)∪E(G)到{1,2,…,k}的映射,對任意的u∈V(G),若uv∈E(G),則u關(guān)于v的色集合記為Cv(u)={f(u)}∪{f(v)}∪{f(uw)｜ uw∈E(G),w∈V(G)},如果
　　 (1)對任意的uv,vw∈E

3、(G),u≠w,有,f(uv)≠f(vw)；
　　 (2)對任意的uv∈E(G),有,f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv)；
　　 (3)對任意的uv∈E(G),有Cv(u)≠Cu(v)；
　　 則稱f是G的k-第二類鄰點可區(qū)別全染色(Second—adjacent—vertex-distinguishing total coloring)(簡記為k-SAVDTC).稱min{k｜G有k