邊面列染色和群染色.pdf

1、設G為圖，L(e)，L(f)是圖G的邊和面可選的顏色列，其中｜L(e)｜=｜L(f)｜=k。圖G的k-邊面列染色是對任意L(e)，L(f)，總可在它們各自的列中選一個顏色使得E(G)∪ F(G)中相鄰和關聯(lián)的元素染不同的顏色。G是k-邊面列可染的當且僅當G存在一個k-邊面列染色。G的k-邊面列染色數(shù)(邊面選擇數(shù))是最小的k使得G是k-邊面列可染的，記作X<,l><'ef>(G)。本文證明了對△≥7的Halin圖,x<,l><'ef>(G

2、)=△(G)．對△≥5且最小度大于等于2的連通的系列平行圖，x<,l><'ef>(G)≤△(G)+2。設G為圖，圖G的群A-染色是對圖G的任意的定向，任意的f ∈F(G，A)，其中F(C,A)表示E(G)→A的所有函數(shù)的集合，A是任意的非平凡的Abelian群，總存在一個函數(shù)c:v(G)→A，使得任意的弧e=(x，y)∈E(G)均有c(x)-c(y)≠f(e)。G是A-可染的當且僅當G存在A-染色。圖G的群染色數(shù)是最小的m使得G是A-可