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

楊 瀾，陳祥恩

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

1 預備知識

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

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

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

給定圖G的一個E-全染色，規定以下記號：

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

2 主要結果及其證明

證明先證K8，n不存在12-VDET染色.假設K8，n有1個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中某些頂點的色集合，則X中每個顏色為1的點的色集合至少同時包含10，11，12中的2種色，不妨設為10和11.

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

b.若{2，10，11}，{2，10，12}，{2，11，12}中恰有2個或1個是Y中某些頂點的色集合，則X中每個顏色為2的點的色集合至少同時包含10，11，12中的1種色，不妨設為a，且a∈{10，11，12}.由于{10，11}∩{a}=?，因此a=12.此時只有以下集合可以作為X中頂點的色集合：{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個集合不能區分X中的8個頂點，矛盾.

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

a.若{2，10，11}，{2，10，12}，{2，11，12}都是Y中某些頂點的色集合，則X中每個顏色為2的點的色集合至少同時包含10，11，12中的2種色，不妨設為a和b，且a，b∈{10，11，12}.由于{10}∩{a，b}=?，故{a，b}={11，12}，此時只有以下集合可以作為X中頂點的色集合：{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個集合不能區分X中的8個頂點，矛盾.

b.若{2，10，11}，{2，10，12}，{2，11，12}中恰有2個或1個是Y中某些頂點的色集合，則X中每個顏色為2的點的色集合至少包含10，11，12中的1種色，不妨設為a，且a∈{10，11，12}.由于{10}∩{a}=?，否則X中每個頂點的色集合同時包含顏色10，與假設矛盾，因此a=11或a=12.不妨設前者成立，此時只有以下集合可以作為X中頂點的色集合：{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個集合不能區分X中的8個頂點，矛盾.

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

則

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

情形2.3 當X中每個頂點的色集合至少同時包含3，4，…，12中的8種色，不妨設為3，4，5，6，7，8，9，10，此時只有以下集合可以作為X中頂點的色集合：{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個集合不能區分X中的8個頂點，矛盾.

故當3 975≤n≤7 769時，矛盾.

首先，確定X中頂點的色集合，以及X中每個頂點的顏色.令：

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中頂點的色集合.讓頂點v1，v2，…，v7 769分別對應下列色集合：含顏色{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}.

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

表1 K8，7 769的頂點vj(1≤j≤7 769)及其關聯邊的染色方案