齒輪圖的星邊染色

張東翰

(商洛學(xué)院 數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西 商洛 726000)

1 主要定義和引理

圖G的一條邊e稱為被剖分，是指刪除其并加上連接其2個(gè)端點(diǎn)的一條長為2的路.

2 主要結(jié)果

f(v0vi)=i(i=1,2,3),f(v1u1)=3,f(v2u2)=1,f(v3u3)=2,f(u1v2)=f(u2v3)=f(u3v1)=4，

證畢.

情形1v1u1染顏色2

u1v2只能從集合{1,3,4}中選擇顏色.當(dāng)u1v2染顏色1時(shí)，那么v0v1u1v2v0是一個(gè)2-色圈，矛盾.當(dāng)u1v2染顏色3時(shí)， 那么v1u1v2v0v3是一個(gè)2-色路，矛盾.當(dāng)u1v2染顏色4時(shí)，那么v1u1v2v0v4是一個(gè)2-色路，矛盾.因此,v1u1不能染顏色2.

情形2v1u1染顏色3

u1v2只能從集合{1,4}中選擇顏色.當(dāng)u1v2染顏色1時(shí)，那么v2u1v1v0v3是一個(gè)2-色路，矛盾.當(dāng)u1v2染顏色4時(shí)，v2u2只能從集合{1,3}中選擇顏色，分v2u2染顏色3和v2u2染顏色1兩種情況討論.

情形1)v2u2染顏色3

u2v3只能從集合{1,2,4}中選擇顏色.當(dāng)u2v3染顏色1時(shí)，那么v1v0v3u2v2是一個(gè)2-色路，矛盾.當(dāng)u2v3染顏色2時(shí)，那么v2u2v3v0v2是一個(gè)2-色圈，矛盾.當(dāng)u2v3染顏色4時(shí)，那么v2u2v3v0v4是一個(gè)2-色路，矛盾.

情形2)v2u2染顏色1

為了保證星邊染色的條件，很容易看出u2v3只能染顏色4，v3u3只能染顏色2，u3v4只能染顏色1,v4u4只能從集合{2,3}中選擇顏色.當(dāng)v4u4染顏色2時(shí)，那么u4v4v0v2u1是一個(gè)2-色路，矛盾.當(dāng)u4v1染顏色3時(shí)，那么u4v4v0v3u2是一個(gè)2-色路，矛盾.

因此，v1u1不能染顏色3.

情形3v1u1染顏色4

此時(shí)可以用情形2相同的分析方法而得出矛盾.

f(v0vi)=i(i=1,2,3,4),f(v1u1)=f(u2v3)=4,f(u4v1)=f(u1v2)=3,

f(v3u3)=f(v4u4)=5,f(v2u2)=1,f(u3v4)=2,

證畢.

f(v0vi)=i(i=1,2,3,4,5),f(v1u1)=f(v4u4)=3,f(u1v2)=f(u5v1)=4,

f(v2u2)=f(u4v5)=1,f(u2v3)=f(u3v4)=5,f(v3u3)=f(v5u5)=2,

證畢.

證明根據(jù)引理2～4，可知當(dāng)時(shí)3≤n≤5，結(jié)論成立. 下面證明當(dāng)n≥6時(shí)，結(jié)論也成立.

f(v0vi)=i(i=1,…,n),f(v1u1)=3,f(u1v2)=4,
f(v2u2)=1,f(u2v3)=5,f(v3u3)=2,f(u3v4)=5,

綜上所述，定理1成立.

證畢.