圖的2距離染色.pdf

1、本文僅考慮無向有限簡單圖.對于一個給定的圖G，圖G的頂點集，邊集，最大度，最小度以及G中頂點u，v間的距離分別用V(G)，E(G)，△(G)，δ(G)和dG（u，v）來表示.
　　如果能將一個圖G畫到平面上并使它的邊只在頂點處相交，那么稱該圖G為平面圖.約定:本文所指的平面圖已是一個平面嵌入.用F(G)表示平面圖G的面集.對(V)x∈V(G)∪F(G)，G中x的度用dG（x）來表示，簡記為d(x).
　　圖G的k-2-距離染

2、色是指映射ψ:V(G)→{1，2,…，k}，滿足:若0＜dG(u，v)≤2，有|ψ(u）-ψ（v）|≥1.稱x2(G)=min{k|G有一個k-2-距離染色}為圖G的2-距離色數(shù).
　　圖的L(1，1)-標號是指映射φ:V(G)→{0，1，2，…，k}，滿足:當dG(u，v)=1時，|φ(u)-φ(u)|≥1;當dG(u，v)=2時，|φ(u)-φ(v)|≥1.類似地，把標號數(shù)定義為λp，q(G).
　　圖G的一個頂點列表配

3、置L={L(v)|v∈V(G)｝是一個顏色集合簇.若G的一個正常頂點染色ψ滿足ψ(v)∈L(v)，(V)v∈V(G)，則稱ψ是G的一個L-染色或稱G是L-可染的.若對G的任何一個配置列表L滿足|L(v)|≥k((V)v∈V(G))，G都是L-可染的，則稱G是k-可選的.稱ch(G)=min{k|G是k-可選的}為G的頂點列表色數(shù).類似地，用ch2(G)來表示圖G的L-2-距離色數(shù).
　　本論文分為四章，主要研究在不含短圈條件下的圖