A polynomial algorithm for finding (g,f)-colorings orthogonal to stars in bipartite graphs  

作　　者：LIU Guizhen & DENG Xiaotie Department of Mathematics, Shandong University, Jinan 250100, China Department of Computer Science, The City University of Hong Kong, Hong Kong, China 

出　　处：《Science China Mathematics》2005年第3期322-332,共11页中国科学：数学（英文版）

基　　金：This work was patially suported by a research grant(CityU1056/01E)of Hong Kong Research Grant Council;the National Natural Science Foundation of China(Grants No.19831080,60172003);NSFSD(Z2000A02).

摘　　要：Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two nonnegative integer-valued functions defined on V(G) such that g(x) ≤f(x)for every vertex x of V(G). A(g,f)-coloring of G is a generalized edge-coloring in which each color appears at each vertex x at least g(x) and at most f(x) times. In this paper a polynomial algorithm to find a(g, f)-coloring of a bipartite graph with some constraints using the minimum number of colors is given. Furthermore, we show that the results in this paper are best possible.Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two nonnegative integer-valued functions defined on V(G) such that g(x)≤ f(x) for every vertex x of V(G). A (g. f)-coloring of G is a generalized edge-coloring in which each color appears at each vertex x at least g(x) and at most f(x) times. In this paper a polynomial algorithm to find a (g. f)-coloring of a bipartite graph with some constraints using the minimum number of colors is given. Furthermore, we show that the results in this paper are best possible.

关 键 词：BIPARTITE graph  (g  f)-coloring  (g  f)-factor  ORTHOGONAL coloring. 

分 类 号：O157.5[理学—数学]