圖的距離為2的點可區(qū)別邊染色.pdf

1、圖G的正常k邊染色是指存在一個映射φ:E(G)→{1，2，…，k}，使得相鄰的邊e和e'滿足φ(e)≠φ(e').令Cφ(v)表示與點v相關聯(lián)的邊的顏色所構成的顏色集合，即Cφ(v)={φ(uv)|uv∈E(G)}.圖G的距離為2的點可區(qū)別邊染色是指，G的一個正常邊染色滿足對任意的兩個距離為2的頂點u和v，都有Cφ(u)≠Cφ(v).圖G的距離為2的點可區(qū)別邊色數(shù)x'd2(G)是指G有一個距離為2的點可區(qū)別k-邊染色的最小k值.

2、　　圖的距離為2的點可區(qū)別邊染色是r-強邊染色的一種特殊情形.圖的r-強邊染色是由Akbari等人和Zhang等人在2006年分別獨立提出的.設r≥1是一個整數(shù)，圖G的r-強邊色數(shù)x's(G，r)是指G的一個正常邊染色φ滿足對任意兩個頂點u和v，若d(u，v)≤r，都有Cφ(u)≠Cφ(v)的最小顏色數(shù).
　　若r=1，則x's(G，1)=x'a(G)，x'a(G)被稱為鄰點可區(qū)別邊色數(shù).鄰點可區(qū)別邊染色最早是由Zhang，Liu

3、和Wang在2002年提出的，他們猜想:若G是一個|V(G)|≥6的連通圖，則有x'a(G)≤△+2.Balister等人證明了猜想對二部圖和最大度不大于3的圖是成立的.Hatami運用概率方法證明了對每一個△＞1020的圖G，都有x'a(G)≤△+300.Akbari，Bidkhori和Nosrati證明了對每一個圖G，都有x'a(G)≤3△.隨后Wang等人將這個界進行了改進，證明了對任意的圖G，x'a(G)≤2.5△.
　　

4、本學位論文主要研究了圖的距離為2的點可區(qū)別邊染色問題，共分四章.
　　在第一章中，介紹了基本概念和相關領域的研究現(xiàn)狀，并且呈現(xiàn)了本文的主要結果.
　　在第二章中，研究了特殊圖類的距離為2的點可區(qū)別邊染色，確定了一些簡單圖類、單圈圖以及兩類積圖的距離為2的點可區(qū)別邊色數(shù).
　　在第三章中，研究了哈林圖的距離為2的點可區(qū)別邊染色，證明了哈林圖的距離為2的點可區(qū)別邊色數(shù)的上界是△+2.
　　在第四章中，研究了外平面圖的