完全二部圖K_6,n當n較小時的點可區別IE-全染色

【摘要】設G是簡單圖，圖G的一個k駁憧汕別IE踩染色（簡記為k睼DIET染色），f是指一個從V(G)∪E(G)到{1，2，…，k}的映射，且滿足:衭v∈E(G)，有f(u)≠f(v)；衭，v∈V(G)，u≠v，有C(u)≠C(v)，其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.數min{k|G有一個k睼DIET染色}稱為圖G的點可區別IE踩色數，記為χievt(G).本文給出了完全二部圖K6,n(7≤n≤243)的點可區別IE踩色數.

【關鍵詞】圖；點可區別IE踩染色；點可區別IE踩色數；完全二部圖

在文獻［1，2］中，點可區別正常全染色已被研究過，本文將討論一種非正常的點可區別全染色.圖G的一個全染色叫做圖G的正常全染色，如果以下三個條件被滿足，條件(v):相鄰的兩個頂點不能染相同的顏色;條件(e):相鄰的兩條邊不能染相同的顏色;條件(i):任意的點和與之關聯的邊不能染相同的顏色.如果圖G的全染色只滿足條件(v)，這樣的全染色稱為圖G的IE踩染色.如果f是圖G的使用了k中顏色的IE踩染色，且對任意u,v∈V(G)，u≠v，有C(u)≠C(v)，那么f稱為圖G的k駁憧汕別IE踩染色，或k睼DIET染色.數min{k|G有一個k睼DIET染色}稱為圖G的點可區別IE踩色數，記為χievt(G).

對圖G，令ni表示度為i的頂點個數，δ≤i≤Δ.設

【參考文獻】

［1］陳祥恩.n卜教宓牡憧汕別全染色的漸進性態［J］.西北師范大學學報(自然科學版)，2005，41(5):1-3.

［2］Zhang Zhongfu，QIU Pengxiang，XU Baogen，et al.verter瞕istinguishing total colorings of graphs［J］.Ars Combinatoria 2008，87:33-45.

［3］何文玉，陳祥恩.完全二部圖k5,n的點可區別IE踩染色［J］.山東大學學報(理學版)，2009，44(2):91-96.