平面圖鄰接點(diǎn)區(qū)分邊染色的一個結(jié)果.pdf

1、本文主要研究了平面圖的一類推廣的邊染色問題:鄰接點(diǎn)區(qū)分邊染色，所討論的圖均為簡單圖.
　　設(shè)φ:E(G)→{1，2，…，k}是從G的邊集構(gòu)成的集合E(G)到自然數(shù)集的一個映射，如果對任意相鄰接的兩個元素x，y∈E(G)均有φ（x)≠φ（y），則稱φ是G的一個正常邊染色.
　　鄰接點(diǎn)區(qū)分染色是邊染色的一中推廣，這種染色對于圖G的邊可選用的顏色有一定的限制.我們用Cφ(v)來表示與頂點(diǎn)v相關(guān)聯(lián)的邊的顏色集合，即Cφ(v)={φ(

2、uv)|uv∈E(G)}.如果φ是圖G的一個正常邊染色，同時對任意一對鄰接點(diǎn)u和v滿足Cφ(u)≠Cφ(v)，則稱φ是圖G的一個鄰接點(diǎn)區(qū)分邊染色.我們用X'avd(G)來表示圖G的鄰接點(diǎn)區(qū)分邊染色數(shù)，它是使得圖G是鄰接點(diǎn)區(qū)分邊可染的最小的正整數(shù)k，即X'avd(G)=min{k|G是k-鄰接點(diǎn)區(qū)分邊可染的}.
　　Zhang等人[22]完全解決了路，圈，樹，完全圖和完全二部圖的鄰接點(diǎn)區(qū)分邊染色問題，并提出一個重要猜想:如果圖G是一

3、個頂點(diǎn)數(shù)至少是3的連通圖，且不是長為5的圈，那么圖G的鄰接點(diǎn)區(qū)分邊染色數(shù)將不會超過△(G)+2.Balister, Hatami，卜月華，王維凡等人通過對圖的最大平均度，可平面圖的圍長，最大度等的討論，對這一猜想進(jìn)行了一系列研究.其中卜月華，王維兒等人證明該猜想對圍長至少為6的平面圖是正確的.在本文中，我們將在卜月華，王維凡等人關(guān)于圍長至少為6的平面圖的一些結(jié)論的基礎(chǔ)上，進(jìn)一步把圍長縮小至5，得到如下結(jié)論:
　　若圖G是一個沒有孤