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

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

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

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