簡單圖的鄰和可區(qū)別邊染色.pdf

1、對于圖G=(V, E)，它的正[k]-邊染色指的是G的邊集E到顏色集C=[k]={1,2,…，k}的映射ψ，若對于任意兩條相互關聯(lián)的邊(∨)e1,e2∈E(G)有ψ(e1)≠ψ(e2)，則稱ψ是G的正常[k]-邊染色，我們用x'(G)表示使得G有正常[k]-邊染色的最小整數(shù)k.給定G的正常[k]-邊染色ψ，Sψ(v)表示與v相鄰的邊的權值和，任意uv∈E(G)，有Sψ(u)≠Sψ(v)，稱染色ψ為圖G的鄰和可區(qū)別的[k]-邊染色.我們用

2、x'∑(G)表示使得G有鄰和可區(qū)別的[k]-邊染色的最小整數(shù)k.G的平均度為Σv∈V(G)d(v)/|V(G)|，記為ad(G).最大平均度mad(G)是G的子圖的平均度的最大值.本文主要證明了兩個定理:
　　定理1如果G是不含孤立邊的mad(G)＜10/3的簡單圖，那么x'∑(G)≤k，其中k=max{△(G)+3,11}.
　　定理2(1)設G是最大度為△，圍長為g的正常平面圖，如果g≥5,則x'∑(G)≤k，其中k=m

3、ax{△(G)+3,10}.
　　(2)設G是最大度為△且不含4-圈的正常平面圖，則x'∑(G)≤k，其中當△(G)≠10時，k=max{△(G)+3,13}，當△(G)=10時，k=max{△(G)+3,14}=14.
　　本文主要內容具體分為三章展開:
　　第一章，首先介紹了本文用到的基本定義和符號，其次介紹了相關概念和已得到結果，最后給出了本文要證明的兩個定理.
　　第二章，我們利用權轉移方法證明了定理1.