杨 澜，陈祥恩

(西北师范大学数学与统计学院，甘肃 兰州 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中某些顶点的……