完全二部圖K8，n(3 975≤n≤7 769)的點(diǎn)可區(qū)別E-全染色

楊 瀾，陳祥恩

(西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州 730070)

1 預(yù)備知識(shí)

文獻(xiàn)[5]探討了完全圖，完全二部圖K2，n、星、輪、扇、路和圈的VDET染色.文獻(xiàn)[6]得出了mC3和mC4的VDET色數(shù).文獻(xiàn)[7-9]中討論了完全二部圖K3，n，K4，n，K5，n的VDET染色.文獻(xiàn)[10]討論了完全二部圖K7，n的VDET染色.本文主要討論K8，n(3 975≤n≤7 769)的VDET染色并得到了K8，n的VDET色數(shù).

本文中，令V(K8，n)=X∪Y，E(K8，n)={uivj|1≤i≤8，1≤j≤n}，其中

X={u1，u2，…，u8}，Y={v1，v2，…，vn}.

給定圖G的一個(gè)E-全染色，規(guī)定以下記號(hào)：

C(X)={C(u1)，C(u2)，…，C(u8)}，C(Y)={C(v1)，C(v2)，…，C(vn)}.

2 主要結(jié)果及其證明

證明先證K8，n不存在12-VDET染色.假設(shè)K8，n有1個(gè)12-VDET染色f，所用顏色分別為1，2，3，4，5，6，7，8，9，10，11，12.考慮以下3種情形：

(ⅰ) {1，10，11}，{1，10，12}，{1，11，12}都是Y中某些頂點(diǎn)的色集合，則X中每個(gè)顏色為1的點(diǎn)的色集合至少同時(shí)包含10，11，12中的2種色，不妨設(shè)為10和11.

a.若{2，10，11}，{2，10，12}，{2，11，12}都是Y中某些頂點(diǎn)的色集合，則X中每個(gè)顏色為2的點(diǎn)的色集合至少同時(shí)包含10，11，12中的2種色，不妨設(shè)為a和b，且a，b∈{10，11，12}.由于{10，11}∩{a，b}≠?，因此X中每個(gè)頂點(diǎn)的色集合同時(shí)包含10，11中的至少1種色，與假設(shè)矛盾.

b.若{2，10，11}，{2，10，12}，{2，11，12}中恰有2個(gè)或1個(gè)是Y中某些頂點(diǎn)的色集合，則X中每個(gè)顏色為2的點(diǎn)的色集合至少同時(shí)包含10，11，12中的1種色，不妨設(shè)為a，且a∈{10，11，12}.由于{10，11}∩{a}=?，因此a=12.此時(shí)只有以下集合可以作為X中頂點(diǎn)的色集合：{1，2，3，4，5，6，7，8，9，10，11}，{1，2，3，4，5，6，7，8，9，10，11，12}，{1，2，3，4，5，6，7，8，9，12}，{1，2，3，4，5，6，7，8，9，10，12}，{1，2，3，4，5，6，7，8，9，11，12}.5個(gè)集合不能區(qū)分X中的8個(gè)頂點(diǎn)，矛盾.

(ⅱ) {1，10，11}，{1，10，12}，{1，11，12}中恰有2個(gè)或1個(gè)是Y中某些頂點(diǎn)的色集合，則X中每個(gè)顏色為1的點(diǎn)的色集合至少同時(shí)包含10，11，12中的1種色，不妨設(shè)為10.此時(shí){2，10，11}，{2，10，12}，{2，11，12}中至多有2個(gè)不是Y中某些頂點(diǎn)的色集合.

a.若{2，10，11}，{2，10，12}，{2，11，12}都是Y中某些頂點(diǎn)的色集合，則X中每個(gè)顏色為2的點(diǎn)的色集合至少同時(shí)包含10，11，12中的2種色，不妨設(shè)為a和b，且a，b∈{10，11，12}.由于{10}∩{a，b}=?，故{a，b}={11，12}，此時(shí)只有以下集合可以作為X中頂點(diǎn)的色集合：{1，2，3，4，5，6，7，8，9，10}，{1，2，3，4，5，6，7，8，9，10，11}，{1，2，3，4，5，6，7，8，9，10，12}，{1，2，3，4，5，6，7，8，9，10，11，12}，{1，2，3，4，5，6，7，8，9，11，12}.5個(gè)集合不能區(qū)分X中的8個(gè)頂點(diǎn)，矛盾.

b.若{2，10，11}，{2，10，12}，{2，11，12}中恰有2個(gè)或1個(gè)是Y中某些頂點(diǎn)的色集合，則X中每個(gè)顏色為2的點(diǎn)的色集合至少包含10，11，12中的1種色，不妨設(shè)為a，且a∈{10，11，12}.由于{10}∩{a}=?，否則X中每個(gè)頂點(diǎn)的色集合同時(shí)包含顏色10，與假設(shè)矛盾，因此a=11或a=12.不妨設(shè)前者成立，此時(shí)只有以下集合可以作為X中頂點(diǎn)的色集合：{1，2，3，4，5，6，7，8，9，10}，{1，2，3，4，5，6，7，8，9，10，11}，{1，2，3，4，5，6，7，8，9，10，12}，{1，2，3，4，5，6，7，8，9，10，11，12}，{1，2，3，4，5，6，7，8，9，11}，{1，2，3，4，5，6，7，9，11，12}.6個(gè)集合不能區(qū)分X中的8個(gè)頂點(diǎn)，矛盾.

(ⅲ) {1，10，11}，{1，10，12}，{1，11，12}均不是Y中任一頂點(diǎn)的色集合，即

則

有8+n≤3 983-8+7，可得n≤3 984，矛盾.

情形2.3 當(dāng)X中每個(gè)頂點(diǎn)的色集合至少同時(shí)包含3，4，…，12中的8種色，不妨設(shè)為3，4，5，6，7，8，9，10，此時(shí)只有以下集合可以作為X中頂點(diǎn)的色集合：{1，2，3，4，5，6，7，8，9，10}，{1，2，3，4，5，6，7，8，9，10，11}，{1，2，3，4，5，6，7，8，9，10，12}，{1，2，3，4，5，6，7，8，9，10，11，12}.4個(gè)集合不能區(qū)分X中的8個(gè)頂點(diǎn)，矛盾.

故當(dāng)3 975≤n≤7 769時(shí)，矛盾.

首先，確定X中頂點(diǎn)的色集合，以及X中每個(gè)頂點(diǎn)的顏色.令：

C(u1)={1，2，6，7，8，9，10，11，12，13}，f(u1)=2；

C(u2)={1，2，3，6，7，8，9，10，11，12，13}，f(u2)=2；

C(u3)={1，2，4，6，7，8，9，10，11，12，13}，f(u3)=2；

C(u4)={1，2，5，6，7，8，9，10，11，12，13}，f(u4)=2；

C(u5)={1，2，3，4，6，7，8，9，10，11，12，13}，f(u5)=2；

C(u6)={1，2，3，5，6，7，8，9，10，11，12，13}，f(u6)=2；

C(u7)={1，2，4，5，6，7，8，9，10，11，12，13}，f(u7)=1；

C(u8)={1，2，3，4，5，6，7，8，9，10，11，12，13}，f(u8)=1.

其次，確定Y中頂點(diǎn)的色集合.讓頂點(diǎn)v1，v2，…，v7 769分別對應(yīng)下列色集合：含顏色{3，4，5，6，7，8，9，10，11，12，13}的2-子集但不是{3，4}，{3，5}，{4，5}；含顏色{1，2，3，4，5，6，7，8，9，10，11，12，13}的3-子集、4-子集、5-子集、6-子集、7-子集、8-子集、9-子集，但不是{2，3，4}，{2，3，5}，{2，4，5}，{3，4，5}，{2，3，4，5}.

頂點(diǎn)vj(1≤j≤7 769)和它的關(guān)聯(lián)邊u1vj，u2vj，…，u8vj的具體染色方案在表1中給出.

表1 K8，7 769的頂點(diǎn)vj(1≤j≤7 769)及其關(guān)聯(lián)邊的染色方案