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.展开更多
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.展开更多
An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v V（G） at most f（v） times. The minimum number of colors needed to f-color G is called the f-chromatic index of G and...An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v V（G） at most f（v） times. The minimum number of colors needed to f-color G is called the f-chromatic index of G and is denoted by X′f（G）. Any simple graph G has the f-chromatic index equal to △f（G） or △f（G） ＋ 1, where △f（G） =max v V（G）{[d（v）/f（v）]}. If X′f（G） = △f（G）, then G is of f-class 1; otherwise G is of f-class 2. In this paper, a class of graphs of f-class 1 are obtained by a constructive proof. As a result, f-colorings of these graphs with △f（G） colors are given.展开更多
Abstract An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v ∈ V（G） at most f（v） times. The f-core of G is the subgraph of G induced by the vertices v of degree d（v...Abstract An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v ∈ V（G） at most f（v） times. The f-core of G is the subgraph of G induced by the vertices v of degree d（v） = f（v）maxv∈y（G）{ [d（v）/f（v）l}. In this paper, we find some necessary conditions for a simple graph, whose f-core has maximum degree two, to be of class 2 for f-colorings.展开更多
随机图 G( n,p)是具有 n 个标号的顶点的图,并且图中的每一顶点对都以概率 p 被随机且独立地选择为图 G 的边。特别地,当 p =2/1时,得到一个概率空间,其中 n 个顶点上的所有标号图是等概率的。对于有顶点集 V 和边集 E 的简单图 G =( V,...随机图 G( n,p)是具有 n 个标号的顶点的图,并且图中的每一顶点对都以概率 p 被随机且独立地选择为图 G 的边。特别地,当 p =2/1时,得到一个概率空间,其中 n 个顶点上的所有标号图是等概率的。对于有顶点集 V 和边集 E 的简单图 G =( V,E),G 的 f-染色 c 是广义的边染色,使每个颜色类在任一顶点 v 上至多出现 f( v)次,其中 f(v)是分配给 v 的正整数。给出随机图 G (n,2/1)是 f-第一类的一个充分条件。展开更多
Let G be a multigraph with vertex set V（G）. Assume that a positive integer f（v） with 1 ≤ f（v） ≤ d（v） is associated with each vertex v ∈ V. An edge coloring of G is called an f-edge cover-coloring, if each c...Let G be a multigraph with vertex set V（G）. Assume that a positive integer f（v） with 1 ≤ f（v） ≤ d（v） is associated with each vertex v ∈ V. An edge coloring of G is called an f-edge cover-coloring, if each color appears at each vertex v at least f（v） times. Let X＇fc（G） be the maximum positive integer k for which an f-edge cover-coloring with k colors of G exists. In this paper, we give a new lower bound of X＇fc（G）, which is sharp.展开更多
基金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.
基金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.
基金NSFC (10471078,60673047)RSDP (20040422004)NSF of Hebei(A2007000002) of China
文摘An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v V（G） at most f（v） times. The minimum number of colors needed to f-color G is called the f-chromatic index of G and is denoted by X′f（G）. Any simple graph G has the f-chromatic index equal to △f（G） or △f（G） ＋ 1, where △f（G） =max v V（G）{[d（v）/f（v）]}. If X′f（G） = △f（G）, then G is of f-class 1; otherwise G is of f-class 2. In this paper, a class of graphs of f-class 1 are obtained by a constructive proof. As a result, f-colorings of these graphs with △f（G） colors are given.
基金Supported by National Natural Science Foundation of China(Grant Nos.10901097,11001055)Tianyuan Youth Foundation of Mathematics(Grant No.10926099)+1 种基金Natural Science Foundation of Shandong(Grant No.ZR2010AQ003)Shandong Province Higher Educational Science and Technology Program(Grant No.G13LI04)of China
文摘Abstract An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v ∈ V（G） at most f（v） times. The f-core of G is the subgraph of G induced by the vertices v of degree d（v） = f（v）maxv∈y（G）{ [d（v）/f（v）l}. In this paper, we find some necessary conditions for a simple graph, whose f-core has maximum degree two, to be of class 2 for f-colorings.
文摘随机图 G( n,p)是具有 n 个标号的顶点的图,并且图中的每一顶点对都以概率 p 被随机且独立地选择为图 G 的边。特别地,当 p =2/1时,得到一个概率空间,其中 n 个顶点上的所有标号图是等概率的。对于有顶点集 V 和边集 E 的简单图 G =( V,E),G 的 f-染色 c 是广义的边染色,使每个颜色类在任一顶点 v 上至多出现 f( v)次,其中 f(v)是分配给 v 的正整数。给出随机图 G (n,2/1)是 f-第一类的一个充分条件。
文摘Let G be a multigraph with vertex set V（G）. Assume that a positive integer f（v） with 1 ≤ f（v） ≤ d（v） is associated with each vertex v ∈ V. An edge coloring of G is called an f-edge cover-coloring, if each color appears at each vertex v at least f（v） times. Let X＇fc（G） be the maximum positive integer k for which an f-edge cover-coloring with k colors of G exists. In this paper, we give a new lower bound of X＇fc（G）, which is sharp.
