Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let 5 denote the minimum degree of G. We show that if Iv（G）I 〉 （σ2 ＋ 14σ ＋ 1）/4, then G...Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let 5 denote the minimum degree of G. We show that if Iv（G）I 〉 （σ2 ＋ 14σ ＋ 1）/4, then G has a rainbow matching of size 6, which answers a question asked by G. Wang [Electron. J. Combin., 2011, 18： #N162] affirmatively. In addition, we prove that if G is a properly colored bipartite graph with bipartition （X, Y） and max{lXl, IYI} 〉 （σ2 ＋ 4σ - 4）/4, then G has a rainbow matching of size σ.展开更多
In this paper,by constructing the current graph of the complete graph K_(12s+9)and a mapping function,we prove that K_(12s+9)(s is an odd number)has at least 6^(2s)×3^(s+3/2) nonisomorphic orientable quadrangular...In this paper,by constructing the current graph of the complete graph K_(12s+9)and a mapping function,we prove that K_(12s+9)(s is an odd number)has at least 6^(2s)×3^(s+3/2) nonisomorphic orientable quadrangular embeddings,and the orientable genus is(12s+9)(12s+4)/8+1.Every one of the nonisomorphic orientable quadrangular embeddings has at least twenty-four 4-edge-colors,and each color appears around each face of orientable quadrangular embeddings.展开更多
Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different c...Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different colors. The cost ?of an edge-coloring f of G is the sum of costs ?of colors ?assigned to all edges e in G. An edge-coloring f of G is optimal if ?is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge- ??coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.展开更多
Let G be a graph and H be a set of subgraphs of G.An h-edge-coloring of G is H-polychromatic if every subgraph of G isomorphic to some element in H receives all h colors.The largest integer h,for which G admits an H-p...Let G be a graph and H be a set of subgraphs of G.An h-edge-coloring of G is H-polychromatic if every subgraph of G isomorphic to some element in H receives all h colors.The largest integer h,for which G admits an H-polychromatic h-edge-coloring,is called the H-polychromatic number of G and denoted by pH(G).In this paper,we prove that pk_(s,t)(K_(m,n))=[m+n-8-t+1/mn]for 2≤s<m,2≤t<n and max{m,n}<s+t,which extends a result of Zhang,Jiang and Zhang that pk_(n-1,n-1)(K_(n,n))=[3/n^(2)].展开更多
A strong k-edge-coloring of a graph G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex, or being adjacent to the same edge of G, axe assigned different colors....A strong k-edge-coloring of a graph G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex, or being adjacent to the same edge of G, axe assigned different colors. The strong chromatic index of G is the smallest integer k for which G has a strong k-edge-coloring. In this paper, we have shown that the strong chromatic index is no larger than 6 for outerplanax graphs with maximum degree 3.展开更多
Generalized balanced tournament designs(GBTDs) are an equivalent characterization of a class of equitable symbol weight codes. Motivated by the construction of GBTDs, we establish in this paper an asymptotic existence...Generalized balanced tournament designs(GBTDs) are an equivalent characterization of a class of equitable symbol weight codes. Motivated by the construction of GBTDs, we establish in this paper an asymptotic existence theorem for frame-GBTDs of type gnand block size k via decompositions of edge-colored complete digraphs into prescribed edge-colored subgraphs.展开更多
A heterochromatie tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by tr （G）, is the minimum positive integer...A heterochromatie tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by tr （G）, is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we determine the heterochromatic tree partition number of r-edge-colored complete graphs. We also find at most tr（Kn） vertex-disjoint heterochromatic trees to cover all the vertices in polynomial time for a given r-edge-coloring of Kn.展开更多
An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path,which contains a color used on exactly one of its edges.The conflict-free connection number of a connected graph G,...An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path,which contains a color used on exactly one of its edges.The conflict-free connection number of a connected graph G,denoted by cf c(G),is defined as the minimum number of colors that are required in order to make G conflict-free connected.In this paper,we investigate the relation between the conflict-free connection number and the independence number of a graph.We firstly show that cf c(G)≤α(G)for any connected graph G,and give an example to show that the bound is sharp.With this result,we prove that if T is a tree with?(T)≥(α(T)+2)/2,then cf c(T)=?(T).展开更多
An edge-coloring of a graph G is an coloring of a graph G is an edge-coloring of G such assignment of colors to all the edges of G. A go- that each color appears at each vertex at least g（v） times. The maximum integ...An edge-coloring of a graph G is an coloring of a graph G is an edge-coloring of G such assignment of colors to all the edges of G. A go- that each color appears at each vertex at least g（v） times. The maximum integer k such that G has a go-coloring with k colors is called the gc-chromatic index of G and denoted by X＇gc （G）. In this paper, we extend a result on edge-covering coloring of Zhang X＇gc（ ） = δg（G）, and Liu in 2011, and give a new sufficient condition for a simple graph G to satisfy ＇ x＇gc（G）=δg（G）,where δg（G）=minv∈V（G）{[d（v）/g（v）]}.展开更多
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.展开更多
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 edge-cut of an edge-colored connected graph is called a rainbow cut if no two edges in the edge-cut are colored the same.An edge-colored graph is rainbow disconnected if for any two distinct vertices u and v of the...An edge-cut of an edge-colored connected graph is called a rainbow cut if no two edges in the edge-cut are colored the same.An edge-colored graph is rainbow disconnected if for any two distinct vertices u and v of the graph,there exists a rainbow cut separating u and v.For a connected graph G,the rainbow disconnection number of G,denoted by rd(G),is defined as the smallest number of colors required to make G rainbow disconnected.In this paper,we first give some upper bounds for rd(G),and moreover,we completely characterize the graphs which meet the upper bounds of the NordhausGaddum type result obtained early by us.Secondly,we propose a conjecture that for any connected graph G,either rd(G)=λ^(+)(G)or rd(G)=λ^(+)(G)+1,whereλ^(+)(G)is the upper edge-connectivity,and prove that the conjecture holds for many classes of graphs,which supports this conjecture.Moreover,we prove that for an odd integer k,if G is a k-edge-connected k-regular graph,thenχ’(G)=k if and only if rd(G)=k.It implies that there are infinitely many k-edge-connected k-regular graphs G for which rd(G)=λ^(+)(G)for odd k,and also there are infinitely many k-edge-connected k-regular graphs G for which rd(G)=λ^(+)(G)+1 for odd k.For k=3,the result gives rise to an interesting result,which is equivalent to the famous Four-Color Problem.Finally,we give the relationship between rd(G)of a graph G and the rainbow vertex-disconnection number rvd(L(G))of the line graph L(G)of G.展开更多
In this paper, the authors have obtained some lower bounds on the size of a 7-critical graph,and some results about the planar graph conjecture have been given.
文摘Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let 5 denote the minimum degree of G. We show that if Iv（G）I 〉 （σ2 ＋ 14σ ＋ 1）/4, then G has a rainbow matching of size 6, which answers a question asked by G. Wang [Electron. J. Combin., 2011, 18： #N162] affirmatively. In addition, we prove that if G is a properly colored bipartite graph with bipartition （X, Y） and max{lXl, IYI} 〉 （σ2 ＋ 4σ - 4）/4, then G has a rainbow matching of size σ.
文摘In this paper,by constructing the current graph of the complete graph K_(12s+9)and a mapping function,we prove that K_(12s+9)(s is an odd number)has at least 6^(2s)×3^(s+3/2) nonisomorphic orientable quadrangular embeddings,and the orientable genus is(12s+9)(12s+4)/8+1.Every one of the nonisomorphic orientable quadrangular embeddings has at least twenty-four 4-edge-colors,and each color appears around each face of orientable quadrangular embeddings.
文摘Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different colors. The cost ?of an edge-coloring f of G is the sum of costs ?of colors ?assigned to all edges e in G. An edge-coloring f of G is optimal if ?is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge- ??coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.
基金Supported by the National Natural Science Foundation of China(Grant No.12071265)the Natural Science Foundation of Shandong Province(Grant No.ZR2025MS11)。
文摘Let G be a graph and H be a set of subgraphs of G.An h-edge-coloring of G is H-polychromatic if every subgraph of G isomorphic to some element in H receives all h colors.The largest integer h,for which G admits an H-polychromatic h-edge-coloring,is called the H-polychromatic number of G and denoted by pH(G).In this paper,we prove that pk_(s,t)(K_(m,n))=[m+n-8-t+1/mn]for 2≤s<m,2≤t<n and max{m,n}<s+t,which extends a result of Zhang,Jiang and Zhang that pk_(n-1,n-1)(K_(n,n))=[3/n^(2)].
基金Supported by the National Natural Science Foundation of China under Grant No.11501050the Fundamental Research Funds for the Central Universities under Grant No.310812151003
文摘A strong k-edge-coloring of a graph G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex, or being adjacent to the same edge of G, axe assigned different colors. The strong chromatic index of G is the smallest integer k for which G has a strong k-edge-coloring. In this paper, we have shown that the strong chromatic index is no larger than 6 for outerplanax graphs with maximum degree 3.
基金supported by National Natural Science Foundation of China(Grant Nos.11271280 and 11201328)Graduate Student Research and Innovation Program of Jiangsu Province(Grant No.CXZZ13 0794)
文摘Generalized balanced tournament designs(GBTDs) are an equivalent characterization of a class of equitable symbol weight codes. Motivated by the construction of GBTDs, we establish in this paper an asymptotic existence theorem for frame-GBTDs of type gnand block size k via decompositions of edge-colored complete digraphs into prescribed edge-colored subgraphs.
基金Supported by the National Natural Science Foundation of China (No.11071130 and 11101378)Zhejiang Innovation Project (Grant No.T200905)Zhejiang Provifenincial Natural Science Foundation of China(Z6090150)
文摘A heterochromatie tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by tr （G）, is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we determine the heterochromatic tree partition number of r-edge-colored complete graphs. We also find at most tr（Kn） vertex-disjoint heterochromatic trees to cover all the vertices in polynomial time for a given r-edge-coloring of Kn.
基金supported by Hunan Education Department Foundation(No.18A382)。
文摘An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path,which contains a color used on exactly one of its edges.The conflict-free connection number of a connected graph G,denoted by cf c(G),is defined as the minimum number of colors that are required in order to make G conflict-free connected.In this paper,we investigate the relation between the conflict-free connection number and the independence number of a graph.We firstly show that cf c(G)≤α(G)for any connected graph G,and give an example to show that the bound is sharp.With this result,we prove that if T is a tree with?(T)≥(α(T)+2)/2,then cf c(T)=?(T).
基金Supported by Shandong Provincial Natural Science Foundation,China(Grant No.ZR2014JL001)the Shandong Province Higher Educational Science and Technology Program(Grant No.J13LI04)the Excellent Young Scholars Research Fund of Shandong Normal University of China
文摘An edge-coloring of a graph G is an coloring of a graph G is an edge-coloring of G such assignment of colors to all the edges of G. A go- that each color appears at each vertex at least g（v） times. The maximum integer k such that G has a go-coloring with k colors is called the gc-chromatic index of G and denoted by X＇gc （G）. In this paper, we extend a result on edge-covering coloring of Zhang X＇gc（ ） = δg（G）, and Liu in 2011, and give a new sufficient condition for a simple graph G to satisfy ＇ x＇gc（G）=δg（G）,where δg（G）=minv∈V（G）{[d（v）/g（v）]}.
基金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.
基金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.
基金Supported by National Natural Science Foundation of China(Grant No.11871034)。
文摘An edge-cut of an edge-colored connected graph is called a rainbow cut if no two edges in the edge-cut are colored the same.An edge-colored graph is rainbow disconnected if for any two distinct vertices u and v of the graph,there exists a rainbow cut separating u and v.For a connected graph G,the rainbow disconnection number of G,denoted by rd(G),is defined as the smallest number of colors required to make G rainbow disconnected.In this paper,we first give some upper bounds for rd(G),and moreover,we completely characterize the graphs which meet the upper bounds of the NordhausGaddum type result obtained early by us.Secondly,we propose a conjecture that for any connected graph G,either rd(G)=λ^(+)(G)or rd(G)=λ^(+)(G)+1,whereλ^(+)(G)is the upper edge-connectivity,and prove that the conjecture holds for many classes of graphs,which supports this conjecture.Moreover,we prove that for an odd integer k,if G is a k-edge-connected k-regular graph,thenχ’(G)=k if and only if rd(G)=k.It implies that there are infinitely many k-edge-connected k-regular graphs G for which rd(G)=λ^(+)(G)for odd k,and also there are infinitely many k-edge-connected k-regular graphs G for which rd(G)=λ^(+)(G)+1 for odd k.For k=3,the result gives rise to an interesting result,which is equivalent to the famous Four-Color Problem.Finally,we give the relationship between rd(G)of a graph G and the rainbow vertex-disconnection number rvd(L(G))of the line graph L(G)of G.
文摘In this paper, the authors have obtained some lower bounds on the size of a 7-critical graph,and some results about the planar graph conjecture have been given.
