最大次数为3的色指数临界图的一种构造

徐继军， 时文俊

(1．郑州师范学院数学与统计学院 河南 郑州450044;

2．郑州大学升达经贸管理学院共同学科部 河南郑州451191)

0 引言

本文考虑的图都是简单图，未定义的术语和符号可参看文［1－2］．

给定一个图G，用E(G)和V(G)表示G的边集和点集．G的顶点v的次数是指G中与v相关联的边的数目，用Δ(G)表示G的最大次数．与点v相邻点的集合记为NG(v)或N(v)．

图G的k-(边)着色是一个映射π:E(G)→{1，2，…，k}，使得G的相邻边没有相同的象［4］．图G的色指数χ'(G)=min{kG有一个k-着色}．1965年，Vizing在［2］中证明了定理:对于任何简单图G，有χ'(G)=Δ(G)或χ'(G)=Δ(G)+1．如果χ'(G)=Δ(G)，称G是1-类的，否则称G是2-类的．如果G是连通的，2-类的，并且对G的每一条边e，都有χ'(G－e)＜χ'(G)，称G是(色指数)临界的．如果临界图G的最大次数是Δ，称G是Δ-临界的．

设 v∈V(G)，若 π 是G的一个具有颜色集{1，2，…，k}的k-着色，令Cπ(v)={π(e)e∈E(G)，e是与v相关联的边}，C'π(v)={1，2，…，k}Cπ(v)．如果 i∈Cπ(v)，则称颜色 i击中 v;如果 i∈C'π(v)，则称 i未击中v或i未在v上表现．显然G的一个k-着色π把E(G)划分成k个不交的颜色类，记为E1，E2，…，Ek，其中对于边e∈Ei有π(e)=i．因此，当i≠ j时，Ei∪Ej的每个连通分支是一条链(开或闭)．如果i∈C'π(v)，j∈{1，2，…，k}，则 Ei∪Ej中包含 v的连通分支是一条起始于 v的(i，j)π-链．当 j∈C'π(v)时，起始于v的(i，j)π-链是一条空链(不包含边)．对于起始于v的(i，j)π-链的另一个端点u(≠v)，如果i和j一个击中u，一个未击中u，我们说这条链终止于u［3］．

1 主要结果

图的四边形扩张的定义在文献［4］中给出过，这里我们根据情况的不同又作了补充．

定义1 设G是最大次数为3的2-连通图，xy，uv∈E(G)．在边xy上添加两个新点a，b，在边uv上添加两个新点c，d，再添加两条新边ad和bc，这样得到的图记作G{xy，uv}，abcda是它的一个四边形．根据边xy和uv是否独立及新点的邻接关系的不同，定义5种类型的四边形扩张:

1)若xy和uv是独立的，且x，v分别与a，d相邻，则称G{xy，uv}是G的Ⅰ-型四边形扩张;

2)若xy和uv是独立的，且x，v分别与a，c相邻，则称G{xy，uv}是G的Ⅱ-型四边形扩张;

3)若xy与uv仅有一个点重合，设y与u重合，且x，v分别与a，d相邻，则称G{xy，yv}是G的Ⅲ-型四边形扩张;

4)若xy与uv仅有一个点重合，设y与u重合，若x，v分别与a，c相邻，则称G{xy，yv}是G的Ⅳ-型四边形扩张;

5)在边xy上依次添加4个新点a，b，d，c，使得a与x相邻，c与y相邻，再添加两条新边ad和bc，所得到的图记作G{xy，xy}，abcda是它的一个四边形，称G{xy，xy}为G的Ⅴ-型四边形扩张．

G{xy，uv}也称G的1-四边形扩张．若 x1y1，u1v1∈E(G{xy，uv})，则称 G{xy，uv}的1-四边形扩张G{xy，uv}{x1y1，u1v1}是G的2-四边形扩张．一般地，如果Q是G的一个(k－1)-四边形扩张的1-四边形扩张，则称Q是G的k-四边形扩张．由于添加的4个点的次数都为3，故四边形扩张保持2次点的个数不变，且4k．令 Qk(G)={Q Q是G的k-四边形扩张}．

定理1 设H=G{xy，uv}，如果G是1-类的，则H也是1-类的．

证明 设H是G的Ⅰ-型四边形扩张．由于G是1-类的，令π是G的一个具有颜色集{i，j，k}的3-着色，不妨设 π(xy)=i．如果π(uv)=i，令σ(xa)=σ(by)=σ(cu)=σ(dv)=i，σ(ad)=σ(bc)=j，σ(ab)=σ(cd)=k，对于H的其他边e，σ(e)=π(e)，则 σ即为H的一个3-着色．如果 π(uv)=j，令 σ(xa)=σ(by)=σ(cd)=i，σ(ab)=σ(cu)=σ(dv)=j，σ(ad)=σ(bc)=k，对于H的其他边e，σ(e)=π(e)，则σ即为H的一个3-着色．如果π(uv)=k，类似可得H的一个3-着色，因此H是1-类的．

注对于其他4种类型的四边形扩张也有同样的结果．

引理1［5－6］设 G 是一 Δ-临界图，xy∈E(G)，π 是 G －xy的一个 Δ-着色，则对任意的 i∈ C'π(x)，j∈C'π(y)，起始于 x 的(i，j)π-链必终止于 y．

定理2 设G是3-临界的，xy和uv是G的两条独立边，π是G－xy的具有颜色集{i，j，k}的一个3-着色．设 i∈C'π(x)，j∈C'π(y)，若边 uv不在起始于 x 的(i，j)π-链上，而在另外一条(i，j)π-开链上，则G{xy，uv}是 1-类的．

证明 若G{xy，uv}是G的Ⅰ-型四边形扩张，则xa，by，uc，vd∈E(G{xy，uv})．由于uv不在起始于x的(i，j)π-链上，而在另外一条(i，j)π-开链上，不妨设 π(uv)=i．在 G －{xy，uv}中，交换起始于 u的(i，j)π-链的颜色，得到 G － {xy，uv}的一个 3-着色 σ 使得 i∈C'σ(v)，j∈C'σ(u)．令 σ(xa)= σ(bc)=σ(vd)=i，σ(yb)=σ(ad)=σ(uc)=j，σ(ab)=σ(cd)=k，这样σ扩充为G{xy，uv}的一个3-着色，因此G{xy，uv}是1-类的．类似可证，若G{xy，uv}是G的Ⅱ-型四边形扩张，G{xy，uv}也是1-类的．

定理3 设G是3-临界的，xy和uv是G的两条独立边，且x，y，u，v中有一个二次点．若G{xy，uv}是2-类的，则 G{xy，uv}=H 是3-临界的．

证明 设W={xa，yb，ab，ad，cd，bc，dv，cu}，则(G－{xy，uv})∪W是G的Ⅰ-型四边形扩张，不妨设d(x)=2，π是G－xy的具有颜色集{1，2，3}一个3-着色，则=1 且 C'π(x)∩C'π(y)=∅．不妨设 C'π(x)={1，2}，C'π(y)={3}．由于 G 是临界的，且 G{xy，uv}是 2-类的，只需证明 W中的每条边都是临界的即可．

情形1 π(uv)=3．

令σ(ad)=σ(bc)=1，σ(ab)=σ(cd)=2，σ(dv)=σ(cu)=σ(yb)=3，对 H 的其他边 e，σ(e)=π(e)，则σ是H－xa的一个3-着色，即xa是H的临界边．同理可证yb，ad，dv，ab是H的临界边．

下证bc，cd，cu是H的临界边．因为H是2-类的，由定理2，边uv在起始于x的(1，3)π-链上，或者经过边 uv的(1，3)π-链是一个圈．

情形1．1 若边uv在起始于x的(1，3)π-链上．

如果起始于x的(1，3)π-链先经过v，在G －{xy，uv}中交换起始于u 的(3，1)π-链的颜色，得到G －{xy，uv}的一个3-着色 σ，使得1∈Cσ'(u)，1∈Cσ'(y)．令 σ(yb)=σ(ad)=σ(cu)=1，σ(xa)=σ(cd)=2，σ(ab)=σ(dv)=3，则σ是H－bc的一个3-着色，即bc是H的临界边．同理可证cd，cu是H的临界边．

情形1．2 若经过边uv的(1，3)π-链是一个圈．

交换起始于 x 的(1，3)π-链的颜色，可得到一着色 σ，使得 C'σ(x)={3，2}，C'σ(y)={1}．令 σ(yb)=σ(ad)=1，σ(ab)=σ(cd)=2，σ(xa)=σ(dv)=σ(cu)=3，则σ是H－bc的一个3-着色，即bc是H的临界边．同理可证cd，cu是H的临界边．

情形2 π(uv)=1或2．不妨设π(uv)=1．

令σ(ab)=σ(dv)=σ(cu)=1，σ(ad)=σ(bc)=2，σ(cd)=σ(yb)=3，对 H 的其他边 e，σ(e)=π(e)，则σ是H－xa的一个3-着色，即xa是H的临界边．同理可证yb，bc，ab，cd，cu，ad是H的临界边．

下证dv是H的临界边．由定理2，边uv在起始于x的(1，3)π-链上，或者经过uv的(1，3)π-链是一个圈．

情形2．1 若边uv在起始于x的(1，3)π-链上．

若起始于x的(1，3)π-链先经过u，在G－{xy，uv}中交换起始于x终止于u的(1，3)π-链的颜色，得到G －{xy，uv}的一个 3-着色 σ，使得 3∈C'σ(x)，3∈C'σ(u)．令 σ(ab)= σ(cd)=1，σ(ad)= σ(bc)=2，σ(xa)=σ(yb)=σ(cu)=3，则σ是H－dv的一个3-着色，即dv是H的临界边．

若起始于x的(1，3)π-链先经过v，在G－{xy，uv}中交换起始于x终止于v的(1，3)π-链的颜色，得到G －{xy，uv}的一个3-着色 σ，使得 3∈C'σ(x)，3∈C'σ(v)．令 σ(ab)= σ(cd)=1，σ(ad)= σ(bc)=2，σ(xa)=σ(yb)=σ(cd)=3，则σ是H－dv的一个3-着色，即dv是H的临界边．

情形2．2 若经过边uv的(1，3)π-链是一个圈．

交换起始于 x 终止于 y 的(1，3)π-链的颜色，可得到 G 的一个 3-着色 σ，使得 C'σ(x)={3，2}，C'σ(y)={1}，令σ(yb)=σ(ad)=σ(cu)=1，σ(ab)=σ(cd)=2，σ(xa)=σ(bc)=3，则 σ 是 H －dv的一个3-着色，即dv是H的临界边．

所有情形被考虑，故W中的每条边都是H的临界边．综上，G{xy，uv}=H是3-临界的．

用类似的方法可证，对Ⅱ-型四边形扩张也有相同的结论．

引理2［4，7］设G是一最大次数为3的图，H是对G的某个点作三角形扩张得到的图，则有(a)G是1-类的当且仅当H是1-类的;(b)G是3-临界的当且仅当H是3-临界的．

定理4 设G是最大次数为3的图，xy和yv是G的两条边，H=G{xy，yv}是G的Ⅲ-型四边形扩张或Ⅳ-型四边形扩张，则(ⅰ)H是1-类的当且仅当G是1-类的;(ⅱ)H是3-临界的当且仅当G是3-临界的．

证明 若H是G的Ⅲ-型四边形扩张，则相当于对图G中的顶点y进行两次三角形扩张，由引理2，结论成立．

现在设H 是 G 的Ⅳ-型四边形扩张，则 E(H)=E(G －{xy，yv})∪{xa，yb，ab，ad，cd，bc，cv，dy}．

(ⅰ)的充分性由定理1的注易得．证明必要性．设H是1-类的，σ是H的一个具有颜色集{1，2，3}的3-着色，先证 σ(xa)≠σ(cv)．事实上，若 σ(xa)=σ(cv)，不妨设 σ(xa)=σ(cv)=1，则{σ(ab)，σ(ad)}={2，3}，{σ(cd)，σ(bc)}={2，3}．这样，边 by和 dy只能着颜色1，矛盾．

若d(y)=2，令π(xy)=σ(xa)，π(yv)=σ(cv)，对G的其他边e，π(e)=σ(e)，则π是G的一个3-着色，因此G是1-类的．

若 d(y)=3，设NG(y)={x，v，p}，我们证明=3．因为 σ(xa)≠σ(cv)，所以只需证明 σ(yp)∉{σ(xa)，σ(cv)}．否则，设 σ(xa)=σ(yp)=1，则{σ(ab)，σ (ad)}={2，3}，{σ(by)，σ(dy)}={2，3}，这样边bc和cd只能着颜色1，矛盾．类似可证σ(yp)≠σ(cv)．令π(xy)=σ(xa)，π (yv)=σ(cv)，π(yp)=σ(yp)，对G的其他边e，π(e)=σ(e)，则π是G的一个3-着色，因此G是1-类的．故(ⅰ)成立．

现在证(ⅱ)．若H是3-临界的，由(ⅰ)知G是2-类的，且G中除了边xy，yv外，其余的边都是临界边．下证xy，yv是G的临界边．设σ是H－xa的一个具有颜色集{1，2，3}的3-着色，则σ(by)= σ(cv)或σ(dy)=σ(cv)．令π(yv)=σ(cv)，对G的其他边e，π(e)=σ(e)，则π即为G－xy的一个3-着色，故xy是G的临界边．同理可证yv是G的临界边．

反之，设G是3-临界的，由(ⅰ)知，H是2-类的且H中除了W中的边以外，其余的边都是临界边．只需证明W中的每条边都是临界边．设π是G－xy的一个具有颜色集{1，2，3}的3-着色，则 C'π(x)=，且 C'π(x)∩C'π(y)= ∅．不妨设 C'π(x)={1}，C'π(y)={2}，π (yv)=1．

令σ(ab)=σ(dy)=σ(cv)=1，σ(by)=σ(cd)=2，σ(ad)=σ(bc)=3，对于H的其他边e，σ(e)=π(e)，则σ为H－xa的一个3-着色，即xa是H的临界边．

同理可证ab，by，ad，bc，dy，cd，cv是H的临界边．故W中的边都是H的临界边，因此H是3-临界的．

定理5 对于Ⅴ-型四边形扩张，设H=G{xy，xy}，则

(A)H是1-类的当且仅当G是1-类的;(B)H是3-临界的当且仅当G是3-临界的．

证明 (A)的充分性由定理1的注易得．设H是1-类的，σ是H的一个具有颜色集{1，2，3}的3-着色，则 σ (xa)=σ (cy)．否则假设 σ (xa)=1，σ (cy)=2，则{σ (ab)，σ (ad)}={1，3}，{σ (cd)，σ(bc)}={2，3}，这样边bd不能用这3种颜色着色，与H是1-类的矛盾．令π(xy)=σ(xa)，对G的其他边e，π(e)=σ(e)，则π为G的一个3-着色，因此G是1-类的．故(A)成立．

现在证(B)．设W={xa，ab，bc，cd，ad，bd，cy}．若H是3-临界的，由(A)知G是2-类的，且G中除了边xy外，其余的边都是临界边．下证xy是G的临界边．

设σ是H－xa的一个具有颜色集{1，2，3}的3-着色，对G－xy的任一边e，令π(e)=σ(e)，则π是G－xy的一个3-着色，故xy是G的临界边．

反之，设G是3-临界的，由(A)知，H是2-类的且H中除了W中的边以外，其余的边都是临界边．只需证明W中的边都是临界边．设π是G－xy的一个具有颜色集{1，2，3}的3-着色，则C'π(x)∩C'π(y)= ∅．不妨设 C'π(x)={1}，C'π(y)={2}．令 σ (ad)= σ (bc)=1，σ (ab)= σ (cd)=2，σ(bd)=σ(cy)=3，对于H的其他边e，σ(e)=π(e)，则σ为H－xa的一个3-着色，即xa是H的临界边．，

同理可证ad，ab，bd，cd，bc，cy是H的临界边．故W中的边都是H的临界边，因此H是3-临界的．

由以上定理的证明可以得到，一简单图G经过一次四边形扩张变换之后，保持图的临界性不变．因此，若已知G是临界图，通过四边形扩张变换可以构造出新的最大次数仍为3的阶数更高的临界图．

［1］ Bondy J A ，Murty U S R．Graph Theory with Application［M］．London and Basingstoke:Macmillan Press，1976:1－103．

［2］ Vizing V G．Critical graphs with a given chromatic class［J］．Diskret Analiz，1965(5):9 －17．

［3］ 谢果．判定K-点连通图与K-边连通图极小性定理［J］．四川师范大学学报:自然科学版，2009，23(5):489－490．

［4］ 时文俊，张利民．图的几个变换［J］．河南师范大学学报:自然科学版，2004，32(4):26－29．

［5］ Yap H P．Some Topics in Graph Theory［M］．London:Cambridge University Press，1986:1 －49．

［6］ 刘广军，刘信生．Pm∨Wn的点可区别全色数［J］．郑州大学学报:理学版，2009，41(1):6－8．

［7］ 董海燕，孙磊，孙艳丽．关于邻点可区别全染色的几个新结果［J］:广西师范大学学报:自然科学版，2005，23(3):41－43．