圖mC8的點可區別Ⅰ-全染色和Ⅵ-全染色

2021-03-23 10:18:32陳祥恩

吉林大學學報(理學版) 2021年2期

楊晗,陳祥恩

(西北師范大學數學與統計學院,蘭州 730070)

1 引言與預備知識

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

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

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

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

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

文獻[14-16]研究了兩條路的聯圖、圈與路的聯圖、圈與圈、圈與輪、圈與扇的聯圖的點可區別Ⅰ-全染色和Ⅵ-全染色. 文獻[17]研究了m個長為4的圈不交并mC4的點可區別全染色. 本文構造m個長為8的圈不交并mC8的最優點可區別Ⅰ-全染色,并確定mC8的點可區別Ⅰ-全色數,當m≥2時,即為ζ(G). 利用命題1確定當m≥2時,mC8的點可區別Ⅵ-全色數. 結果表明,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的某個點可區別Ⅰ-全染色下C8的全體頂點色集合,則稱由這8個元素構成的組是好組.

定義3[17]如果矩陣Ak的4×2階子矩陣B中的諸元素恰是在C8的某個點可區別Ⅰ-全染色下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的點可區別Ⅰ-全染色頂點的色集合,其染色為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的點可區別Ⅰ-全染色頂點的色集合,其染色為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在一種點可區別Ⅰ-全染色下頂點的色集合.

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

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

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

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}.