令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)-染色的一个多项式算法并证明了此结果是最好的可能.
科研之友
微信
新浪微博
Facebook
分享链接
