圖mC8的點可區(qū)別Ⅰ-全染色和Ⅵ-全染色

楊 晗,陳祥恩

(西北師范大學 數(shù)學與統(tǒng)計學院,蘭州 730070)

1 引言與預備知識

本文所考慮的圖均為有限無向簡單圖. 目前,關于圖的點可區(qū)別正常邊染色與圖的點可區(qū)別一般邊染色研究已有很多結果[1-9].

設f:V∪E→{1,2,…,k}為圖G的一個全染色(正?；蛭幢卣?. 對圖G的每個頂點x,用Cf(x)表示在f下點x的顏色及全體與x關聯(lián)的邊的顏色構成的集合(非多重集),稱其為x的色集合或調色板. 設f為圖G的一個正常全染色. 若對?u,v∈V,u≠v,總有C(u)≠C(v),則稱f為G的點可區(qū)別全染色(VDTC)[10-11]. 本文考慮圖的點可區(qū)別的一類未必正常的全染色.

用ni(G)表示圖G的度為i的頂點個數(shù),δ≤i≤Δ,這里δ和Δ分別表示圖G的最小度和最大度. 記

由于圖的點可區(qū)別Ⅰ-全染色必為圖的點可區(qū)別Ⅵ-全染色,故本文只討論圖的點可區(qū)別Ⅰ-全染色,相應的圖的點可區(qū)別Ⅵ-全染色由此可得.

文獻[12]提出了圖的點可區(qū)別Ⅰ-全染色及圖的點可區(qū)別Ⅵ-全染色,并確定了完全圖、完全二部圖、輪、扇、正規(guī)雙星、路、圈、兩條同階圈的聯(lián)圖、一類近完全圖等圖類的點可區(qū)別Ⅰ-全色數(shù)以及點可區(qū)別Ⅵ-全色數(shù),并提出了下列猜想.

文獻[14-16]研究了兩條路的聯(lián)圖、圈與路的聯(lián)圖、圈與圈、圈與輪、圈與扇的聯(lián)圖的點可區(qū)別Ⅰ-全染色和Ⅵ-全染色. 文獻[17]研究了m個長為4的圈不交并mC4的點可區(qū)別全染色. 本文構造m個長為8的圈不交并mC8的最優(yōu)點可區(qū)別Ⅰ-全染色,并確定mC8的點可區(qū)別Ⅰ-全色數(shù),當m≥2時,即為ζ(G). 利用命題1確定當m≥2時,mC8的點可區(qū)別Ⅵ-全色數(shù). 結果表明,VDITC 猜想和VDVITC猜想對圖mC8成立.

首先,對任意的k≥6,構造(k-1)×(k-1)階矩陣Ak,使矩陣Ak的元素是集合{1,2,…,k}的含k的2-子集、3-子集(是即將構造出的某個VDITC下點的色集合,這里的集合不是多重集)或空集,其中第i行含有(i-1)個?:

(1)

定義1[17]設1≤i1

圖1 C8的全染色Fig.1 Total colorings of C8

定義2[17]如果矩陣Ak的8個元素(非空)恰是在C8的某個點可區(qū)別Ⅰ-全染色下C8的全體頂點色集合,則稱由這8個元素構成的組是好組.

定義3[17]如果矩陣Ak的4×2階子矩陣B中的諸元素恰是在C8的某個點可區(qū)別Ⅰ-全染色下C8的8個頂點的色集合,則稱子矩陣B是好的.

將如圖1所示的8階圈全染色記為a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,a. 在該染色下,邊的色下方均有波浪線,而點的色下方沒有波浪線.

引理1當i≡1(mod 4),j≡1(mod 2),且Ak(i,i+1,i+2,i+3|j,j+1)中元素都不是空集時,則Ak(i,i+1,i+2,i+3|j,j+1)為一個好的4×2階子矩陣.

證明: 當i=1時,有

(2)

顯然{k,j},{k,j+1},{k,j,j+1},{k,j,j+2},{k,j,j+3},{k,j+1,j+2},{k,j+1,j+3},{k,j+1,j+4}是C8的點可區(qū)別Ⅰ-全染色頂點的色集合,其染色為k,j+1,j,k,k,j,k,j+2,j+1,k,j,j+3,k,j+1,j+4,k,k. 于是當i=1時,Ak(i,i+1,i+2,i+3|j,j+1)是一個好的子矩陣.

當i≥5時,有

(3)

顯然{k,j,j+i-1},{k,j+1,j+i},{k,j,j+i},{k,j,j+i+1},{k,j,j+i+2},{k,j+1,j+i+1},{k,j+1,j+i+2},{k,j+1,j+i+3}是C8的點可區(qū)別Ⅰ-全染色頂點的色集合,其染色為k,j+i,j+1,k,j+i+3,j+1,k,j+i+2,j,k,j+1,j+i+1,j,k,j+i-1,j,k. 于是當i≥5時,Ak(i,i+1,i+2,i+3|j,j+1)是一個好的子矩陣. 證畢.

由上述證明可知,一個好的子矩陣的所有元素可構成1個好組,它是C8在一種點可區(qū)別Ⅰ-全染色下頂點的色集合.

定義4[17]如果矩陣Ak的元素既不是引理1中好的4×2階子矩陣中的元素,也不是空集,則稱該元素是Ak的剩余元素.

定義5[17]對mC8的一個k-VDITCf,如果{1,2,…,k}的所有2-子集(分別的,3-子集)均為在f下mC8的頂點色集合,則稱2-子集(分別的,3-子集)在f下用完了.

下面給出C8點可區(qū)別Ⅰ-全染色的幾種類型:

1) 類型1的染色為k-2,k-2,k-1,k,k-5,k-1,k-6,k,k-3,k-1,k,k,k-2,k-3,k,k,k-2. 在該染色下,C8頂點的色集合分別為{k,k-3},{k,k-2},{k,k-1},{k,k-3,k-2},{k,k-3,k-1},{k,k-2,k-1},{k,k-5,k-1},{k,k-6,k-1}.

2) 類型2的染色為k-3,k-3,k,k-2,k-2,k,k-3,k-1,k,k-4,k-2,k,k-3,k-4,k,k,k-3. 在該染色下,C8頂點的色集合分別為{k,k-4},{k,k-3},{k,k-2},{k,k-4,k-3},{k,k-4,k-2},{k,k-4,k-1},{k,k-3,k-2},{k,k-3,k-1}.

3) 類型3的染色為j+2,k-2,j,k,k-2,j+1,k,k-1,j,k,j+1,k-3,k,j,k-4,k,j+2. 在該染色下,C8頂點的色集合分別為{k,j,k-4},{k,j,k-3},{k,j,k-2},{k,j,k-1},{k,j+1,k-3},{k,j+1,k-2},{k,j+1,k-1},{k,j+2,k-2}.

4) 類型4的染色為a,k-1,b,k,c,k-1,d,k,e,k-1,f,k,g,k-1,k,k,a. 在該染色下,C8頂點的色集合分別為{k,k-1},{k,a,k-1},{k,b,k-1},{k,c,k-1},{k,d,k-1},{k,e,k-1},{k,f,k-1},{k,g,k-1}.

5) 類型5的染色為a,k-1,b,k,c,k-1,d,k,e,k-1,f,k,g,k-1,h,k,a. 在該染色下,C8頂點的色集合分別為{k,a,k-1},{k,b,k-1},{k,c,k-1},{k,d,k-1},{k,e,k-1},{k,f,k-1},{k,g,k-1},{k,h,k-1}.

6) 類型6的染色為k-2,j+1,k,k-1,j+2,k,k-1,j+4,k,k-2,j+5,k,j+4,k-3,j,k,k-2. 在該染色下,C8頂點的色集合分別為{k,j,k-3},{k,j+1,k-2},{k,j+1,k-1},{k,j+2,k-1},{k,j+4,k-3},{k,j+4,k-2},{k,j+4,k-1},{k,j+5,k-2}.

7) 類型7的染色為k-2,j+4,k,k-1,j+2,k,k-2,j+1,k,k-1,j,k,k-2,j,k-3,k,k-2. 在該染色下,C8頂點的色集合分別為{k,j,k-3},{k,j,k-2},{k,j,k-1},{k,j+1,k-2},{k,j+1,k-1},{k,j+2,k-1},{k,j+4,k-2},{k,j+4,k-1}.

8) 類型8的染色為j+1,k-1,j+5,k,k-2,j+4,k-1,k,k-2,j+3,k-3,k,j+3,k-1,j,k,j+1. 在該染色下,C8頂點的色集合分別為{k,j,k-1},{k,j+1,k-1},{k,j+3,k-3},{k,j+3,k-2},{k,j+3,k-1},{k,j+4,k-1},{k,j+4,k-2},{k,j+5,k-1}.

9) 類型9的染色為j,k-2,k,j+3,k-3,k,j+3,k-1,k,j+4,k-2,k,j+5,k-1,j+1,k,j. 在該染色下,C8頂點的色集合分別為{k,j,k-2},{k,j+1,k-1},{k,j+3,k-3},{k,j+3,k-2},{k,j+3,k-1},{k,j+4,k-1},{k,j+4,k-2},{k,j+5,k-1}.

2 主要結果

由命題1可得: