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...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.展开更多
For two integers k and d with （k, d） = 1 and k≥2d, let G^dk be the graph with vertex set {0,1,…k - 1 } in which ij is an edge if and only if d≤｜ i -j I｜≤k - d. The circular chromatic number χc（G） of a graph...For two integers k and d with （k, d） = 1 and k≥2d, let G^dk be the graph with vertex set {0,1,…k - 1 } in which ij is an edge if and only if d≤｜ i -j I｜≤k - d. The circular chromatic number χc（G） of a graph G is the minimum of k/d for which G admits a homomorphism to G^dk. The relationship between χc（ G- v） and χc （G）is investigated. In particular, the circular chromatic number of G^dk - v for any vertex v is determined. Some graphs withx χc（G - v） =χc（G） - 1 for any vertex v and with certain properties are presented. Some lower bounds for the circular chromatic number of a graph are studied, and a necessary and sufficient condition under which the circular chromatic number of a graph attains the lower bound χ- 1 ＋ 1/α is proved, where χ is the chromatic number of G and a is its independence number.展开更多
Graph coloring has interesting real life applications in optimization and network design. In this paper some new results on the acyclic-edge coloring, f-edge coloring, g-edge cover coloring, （g, f）-coloring and equi...Graph coloring has interesting real life applications in optimization and network design. In this paper some new results on the acyclic-edge coloring, f-edge coloring, g-edge cover coloring, （g, f）-coloring and equitable edge-coloring of graphs are introduced. In particular, some new results related to the above colorings obtained by the authors are given. Some new problems and conjectures are presented.展开更多
The notion of the star chromatic number of a graph is a generalization of the chromatic number. In this paper. we calculate the star chromatic numbers of three infinite families of planar graphs. The first two familie...The notion of the star chromatic number of a graph is a generalization of the chromatic number. In this paper. we calculate the star chromatic numbers of three infinite families of planar graphs. The first two families are derived from a 3-or 5-wheel by subdivisions. their star chromatic numbers being 2+2/(2n + 1). 2+3/(3n + 1)and 2+3/ (3n - 1), respectively. The third family of planar graphs are derived from n odd wheels by Hajos construction with star chromatic numbers 3 + 1/n. which is a generalization of one resnlt of Gao et al.展开更多
The partition problem of a given graph into three independent sets of minimizing the maximum one is studied in this paper.This problem is NP-hard,even restricted to bipartite graphs.First,a simple 3/2-approximation al...The partition problem of a given graph into three independent sets of minimizing the maximum one is studied in this paper.This problem is NP-hard,even restricted to bipartite graphs.First,a simple 3/2-approximation algorithm for any 2-colorable graph is presented.An improved 7/5-approximation algorithm is then designed for a tree.The theoretical proof of the improved algorithm performance ratio is constructive,thus providing an explicit partition approach for each case according to the cardinality of two color classes.展开更多
基金This work was patially suported by a research grant(CityU1056/01E)of Hong Kong Research Grant Councilthe 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.
基金The National Natural Science Foundation of China(No.10671033)
文摘For two integers k and d with （k, d） = 1 and k≥2d, let G^dk be the graph with vertex set {0,1,…k - 1 } in which ij is an edge if and only if d≤｜ i -j I｜≤k - d. The circular chromatic number χc（G） of a graph G is the minimum of k/d for which G admits a homomorphism to G^dk. The relationship between χc（ G- v） and χc （G）is investigated. In particular, the circular chromatic number of G^dk - v for any vertex v is determined. Some graphs withx χc（G - v） =χc（G） - 1 for any vertex v and with certain properties are presented. Some lower bounds for the circular chromatic number of a graph are studied, and a necessary and sufficient condition under which the circular chromatic number of a graph attains the lower bound χ- 1 ＋ 1/α is proved, where χ is the chromatic number of G and a is its independence number.
基金This research is supported by the National Natural Science Foundation of China under Grant Nos. 10871119, 10971121 and Quality Control Standards on Undergraduate Medical Education under Grant No. 200804220001.
文摘Graph coloring has interesting real life applications in optimization and network design. In this paper some new results on the acyclic-edge coloring, f-edge coloring, g-edge cover coloring, （g, f）-coloring and equitable edge-coloring of graphs are introduced. In particular, some new results related to the above colorings obtained by the authors are given. Some new problems and conjectures are presented.
文摘The notion of the star chromatic number of a graph is a generalization of the chromatic number. In this paper. we calculate the star chromatic numbers of three infinite families of planar graphs. The first two families are derived from a 3-or 5-wheel by subdivisions. their star chromatic numbers being 2+2/(2n + 1). 2+3/(3n + 1)and 2+3/ (3n - 1), respectively. The third family of planar graphs are derived from n odd wheels by Hajos construction with star chromatic numbers 3 + 1/n. which is a generalization of one resnlt of Gao et al.
基金gment This work was supported by the National Natural Science Foundation of China(No.11971139)the Natural Science Foundation of Zhejiang Province(No.LY21A010014)the Fundamental Research Funds for the Provincial Universities of Zhejiang(No.GK22990929900)。
文摘The partition problem of a given graph into three independent sets of minimizing the maximum one is studied in this paper.This problem is NP-hard,even restricted to bipartite graphs.First,a simple 3/2-approximation algorithm for any 2-colorable graph is presented.An improved 7/5-approximation algorithm is then designed for a tree.The theoretical proof of the improved algorithm performance ratio is constructive,thus providing an explicit partition approach for each case according to the cardinality of two color classes.
