Let G ： Gn,p be a binomial random graph with n vertices and edge probability p = p（n）, and f be a nonnegative integer-valued function defined on V（G） such that 0 〈 a ≤ f（x） ≤ b 〈 np- 2√nplogn for every ...Let G ： Gn,p be a binomial random graph with n vertices and edge probability p = p（n）, and f be a nonnegative integer-valued function defined on V（G） such that 0 〈 a ≤ f（x） ≤ b 〈 np- 2√nplogn for every E V（G）. An fractional f-indicator function is an function h that assigns to each edge of a graph G a number h（e） in [0, 1] so that for each vertex x, we have d^hG（x） = f（x）, where dh（x） = ∑ h（e） is the fractional degree xEe ofx inG. Set Eh = {e ： e e E（G） and h（e） ≠ 0}. IfGh isaspanningsubgraphofGsuchthat E（Gh） = Eh, then Gh is called an fractional f-factor of G. In this paper, we prove that for any binomial random graph Gn,p 2 with p 〉 n^-2/3, almost surely Gn,p contains an fractional f-factor.展开更多
A vertex coloring of a graph G is called r-acyclic if it is a proper vertex coloring such that every cycle D receives at least min{｜D｜, r} colors. The r-acyclic chromatic number of G is the least number of colors in...A vertex coloring of a graph G is called r-acyclic if it is a proper vertex coloring such that every cycle D receives at least min{｜D｜, r} colors. The r-acyclic chromatic number of G is the least number of colors in an r-acyclic coloring of G. We prove that for any number r ≥ 4, the r-acyclic chromatic number of any graph G with maximum degree △ ≥ 7 and with girth at least（r-1）△ is at most（4r-3）△.展开更多
基金Supported by NSFSD(No.ZR2013AM001)NSFC(No.11001055),NSFC11371355
文摘Let G ： Gn,p be a binomial random graph with n vertices and edge probability p = p（n）, and f be a nonnegative integer-valued function defined on V（G） such that 0 〈 a ≤ f（x） ≤ b 〈 np- 2√nplogn for every E V（G）. An fractional f-indicator function is an function h that assigns to each edge of a graph G a number h（e） in [0, 1] so that for each vertex x, we have d^hG（x） = f（x）, where dh（x） = ∑ h（e） is the fractional degree xEe ofx inG. Set Eh = {e ： e e E（G） and h（e） ≠ 0}. IfGh isaspanningsubgraphofGsuchthat E（Gh） = Eh, then Gh is called an fractional f-factor of G. In this paper, we prove that for any binomial random graph Gn,p 2 with p 〉 n^-2/3, almost surely Gn,p contains an fractional f-factor.
基金supported by NSFC(Grant number 11571258)SDNSF(Grant number ZR2016AM01)
文摘A vertex coloring of a graph G is called r-acyclic if it is a proper vertex coloring such that every cycle D receives at least min{｜D｜, r} colors. The r-acyclic chromatic number of G is the least number of colors in an r-acyclic coloring of G. We prove that for any number r ≥ 4, the r-acyclic chromatic number of any graph G with maximum degree △ ≥ 7 and with girth at least（r-1）△ is at most（4r-3）△.
