中国科学A辑
中國科學A輯
중국과학A집
SCIENCE IN CHINA (SERIES A)
2005年
3期
334-344
,共11页
二部图 (g,f)-染色 (g,f)-因子 正交染色
二部圖 (g,f)-染色 (g,f)-因子 正交染色
이부도 (g,f)-염색 (g,f)-인자 정교염색
令G是一个具有顶点集V(G)和边集E(G)的二部图,且令g和f是定义在V(G)上的两个非负整数值函数,使得对每个顶点x∈V(G)都有g(x)≤f(x).G的一个(g,f)-染色是一个推广的边染色,它满足在每个顶点x每一种颜色至少出现g(x)次且至多出现f(x)次.给出了求二部图中满足某些约束条件且具有最小颜色数的(g,f)-染色的一个多项式算法并证明了此结果是最好的可能.
令G是一箇具有頂點集V(G)和邊集E(G)的二部圖,且令g和f是定義在V(G)上的兩箇非負整數值函數,使得對每箇頂點x∈V(G)都有g(x)≤f(x).G的一箇(g,f)-染色是一箇推廣的邊染色,它滿足在每箇頂點x每一種顏色至少齣現g(x)次且至多齣現f(x)次.給齣瞭求二部圖中滿足某些約束條件且具有最小顏色數的(g,f)-染色的一箇多項式算法併證明瞭此結果是最好的可能.
령G시일개구유정점집V(G)화변집E(G)적이부도,차령g화f시정의재V(G)상적량개비부정수치함수,사득대매개정점x∈V(G)도유g(x)≤f(x).G적일개(g,f)-염색시일개추엄적변염색,타만족재매개정점x매일충안색지소출현g(x)차차지다출현f(x)차.급출료구이부도중만족모사약속조건차구유최소안색수적(g,f)-염색적일개다항식산법병증명료차결과시최호적가능.
