In this paper, we present a new concept of the adjacent-vertex-distinguishing total coloring of graphs (briefly, AVDTC of graphs) and, meanwhile, have obtained the adjacent-vertex-distinguishing total chromatic number...In this paper, we present a new concept of the adjacent-vertex-distinguishing total coloring of graphs (briefly, AVDTC of graphs) and, meanwhile, have obtained the adjacent-vertex-distinguishing total chromatic number of some graphs such as cycle, complete graph, complete bipartite graph, fan, wheel and tree.展开更多
A new concept of the D(β)-vertex-distinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger than β have different color sets, where the color set...A new concept of the D(β)-vertex-distinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger than β have different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it, is proposed in this paper. The D(2)-vertex-distinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented.展开更多
Metasurfaces offer a unique platform to precisely control optical wavefronts and enable the realization of flat lenses,or metalenses,which have the potential to substantially reduce the size and complexity of imaging ...Metasurfaces offer a unique platform to precisely control optical wavefronts and enable the realization of flat lenses,or metalenses,which have the potential to substantially reduce the size and complexity of imaging systems and to realize new imaging modalities.However,it is a major challenge to create achromatic metalenses that produce a single focal length over a broad wavelength range because of the difficulty in simultaneously engineering phase profiles at distinct wavelengths on a single metasurface.For practical applications,there is a further challenge to create broadband achromatic metalenses that work in the transmission mode for incident light waves with any arbitrary polarization state.We developed a design methodology and created libraries of meta-units—building blocks of metasurfaces—with complex cross-sectional geometries to provide diverse phase dispersions(phase as a function of wavelength),which is crucial for creating broadband achromatic metalenses.We elucidated the fundamental limitations of achromatic metalens performance by deriving mathematical equations that govern the tradeoffs between phase dispersion and achievable lens parameters,including the lens diameter,numerical aperture(NA),and bandwidth of achromatic operation.We experimentally demonstrated several dielectric achromatic metalenses reaching the fundamental limitations.These metalenses work in the transmission mode with polarization-independent focusing efficiencies up to 50%and continuously provide a near-constant focal length over λ=1200–1650 nm.These unprecedented properties represent a major advance compared to the state of the art and a major step toward practical implementations of metalenses.展开更多
Integral imaging is a promising three-dimensional(3D)imaging technique that captures and reconstructs light field information.Microlens arrays are usually used for the reconstruction process to display 3D scenes to th...Integral imaging is a promising three-dimensional(3D)imaging technique that captures and reconstructs light field information.Microlens arrays are usually used for the reconstruction process to display 3D scenes to the viewer.However,the inherent chromatic aberration of the microlens array reduces the viewing quality,and thus,broadband achromatic imaging remains a challenge for integral imaging.Here,we realize a silicon nitride metalens array in the visible region that can be used to reconstruct 3D optical scenes in the achromatic integral imaging for white light.The metalens array contains 60×60 polarization-insensitive metalenses with nearly diffraction-limited focusing.The nanoposts in each high-efficiency(measured as 47%on average)metalens are delicately designed with zero effective material dispersion and an effective achromatic refractive index distribution from 430 to 780 nm.In addition,such an achromatic metalens array is composed of only a single silicon nitride layer with an ultrathin thickness of 400 nm,making the array suitable for on-chip hybrid-CMOS integration and the parallel manipulation of optoelectronic information.We expect these findings to provide possibilities for full-color and aberration-free integral imaging,and we envision that the proposed approach may be potentially applicable in the fields of high-power microlithography,high-precision wavefront sensors,virtual/augmented reality and 3D imaging.展开更多
The research and applications of fiber materials are directly related to the daily life of social populace and the development of relevant revolutionary manufacturing industry.However,the conventional fibers and fiber...The research and applications of fiber materials are directly related to the daily life of social populace and the development of relevant revolutionary manufacturing industry.However,the conventional fibers and fiber products can no longer meet the requirements of automation and intellectualization in modern society,as well as people’s consumption needs in pursuit of smart,avant-grade,fashion and distinctiveness.The advanced fiber-shaped electronics with most desired designability and integration features have been explored and developed intensively during the last few years.The advanced fiber-based products such as wearable electronics and smart clothing can be employed as the second skin to enhance information exchange between humans and the external environment.In this review,the significant progress on flexible fiber-shaped multifunctional devices,including fiber-based energy harvesting devices,energy storage devices,chromatic devices,and actuators are discussed.Particularly,the fabrication procedures and application characteristics of multifunctional fiber devices such as fiber-shaped solar cells,lithium-ion batteries,actuators and electrochromic fibers are introduced in detail.Finally,we provide our perspectives on the challenges and future development of functional fiber-shaped devices.展开更多
Let G = （V, E） be a simple connected graph, and ｜V（G）｜ ≥ 2. Let f be a mapping from V（G） ∪ E（G） to {1,2…, k}. If arbitary uv ∈ E（G）,f（u） ≠ f（v）,f（u） ≠ f（uv）,f（v） ≠ f（uv）; arbitary uv, uw...Let G = （V, E） be a simple connected graph, and ｜V（G）｜ ≥ 2. Let f be a mapping from V（G） ∪ E（G） to {1,2…, k}. If arbitary uv ∈ E（G）,f（u） ≠ f（v）,f（u） ≠ f（uv）,f（v） ≠ f（uv）; arbitary uv, uw ∈ E（G）（v ≠ w）, f（uv） ≠ f（uw）;arbitary uv ∈ E（G） and u ≠ v, C（u） ≠ C（v）, whereC（u）={f（u）}∪{f（uv）｜uv∈E（G）}.Then f is called a k-adjacent-vertex-distinguishing-proper-total coloring of the graph G（k-AVDTC of G for short）. The number min{k｜k-AVDTC of G} is called the adjacent vertex-distinguishing total chromatic number and denoted by χat（G）. In this paper we prove that if △（G） is at least a particular constant and δ ≥32√△ln△, then χat（G） ≤ △（G） ＋ 10^26 ＋ 2√△ln△.展开更多
Overcoming chromatic aberrations is a vital concern in imaging systems in order to facilitate fullcolor and hyperspectral imaging.By contrast,large dispersion holds opportunities for spectroscopy and tomography.Combin...Overcoming chromatic aberrations is a vital concern in imaging systems in order to facilitate fullcolor and hyperspectral imaging.By contrast,large dispersion holds opportunities for spectroscopy and tomography.Combining both functions into a single component will significantly enhance its versatility.A strategy is proposed to delicately integrate two lenses with a static resonant phase and a switchable geometric phase separately.The former is a metasurface lens with a linear phase dispersion.The latter is composed of liquid crystals(LCs)with space-variant orientations with a phase profile that is frequency independent.By this means,a broadband achromatic focusing from 0.9 to 1.4 THz is revealed.When a saturated bias is applied on LCs,the geometric phase modulation vanishes,leaving only the resonant phase of the metalens.Correspondingly,the device changes from achromatic to dispersive.Furthermore,a metadeflector with tunable dispersion is demonstrated to verify the universality of the proposed method.Our work may pave a way toward active metaoptics,promoting various imaging applications.展开更多
Up to the present, there are few classes of graphs of which chromatic polynomials can be computed with formulas. For most graphs, computing their chromatic
A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges ...A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to v, where uv ∈E（G）. The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ＇αα（G）, is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G（V, E） is a graph with no isolated edges, then χ＇αα（G）≤32△.展开更多
Let G be a simple graph. A total coloring f of G is called E-total-coloring if no two adjacent vertices of G receive the same color and no edge of G receives the same color as one of its endpoints. For E-total-colorin...Let G be a simple graph. A total coloring f of G is called E-total-coloring if no two adjacent vertices of G receive the same color and no edge of G receives the same color as one of its endpoints. For E-total-coloring f of a graph G and any vertex u of G, let Cf （u） or C（u） denote the set of colors of vertex u and the edges incident to u. We call C（u） the color set of u. If C（u） ≠ C（v） for any two different vertices u and v of V（G）, then we say that f is a vertex-distinguishing E-total-coloring of G, or a VDET coloring of G for short. The minimum number of colors required for a VDET colorings of G is denoted by X^evt（G）, and it is called the VDET chromatic number of G. In this article, we will discuss vertex-distinguishing E-total colorings of the graphs mC3 and mC4.展开更多
Let G be a simple graph. Let f be a mapping from V（G） U E（G） to {1, 2,..., k}. Let Cf（v） = {f（v）} U {f（vw）｜w ∈ V（G）,vw ∈ E（G）} for every v ∈ V（G）. If f is a k-propertotal-coloring, and if Cf（u） ...Let G be a simple graph. Let f be a mapping from V（G） U E（G） to {1, 2,..., k}. Let Cf（v） = {f（v）} U {f（vw）｜w ∈ V（G）,vw ∈ E（G）} for every v ∈ V（G）. If f is a k-propertotal-coloring, and if Cf（u） ≠ Cf（v） for uv ∈ V（G）,uv E E（G）, then f is called k-adjacentvertex-distinguishing total coloring of G（k-AVDTC of G for short）. Let χat（G） = min{k｜G has a k-adjacent-vertex-distinguishing total coloring}. Then χat（G） is called the adjacent-vertex-distinguishing total chromatic number. The adjacent-vertex-distinguishing total chromatic number on the Cartesion product of path Pm and complete graph Kn is obtained.展开更多
Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints....Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C（x） denote the set of colors of vertex x and of the edges incident with x, we call C（x） the color set of x. If C（u） ≠ C（v） for any two different vertices u and v of V （G）, then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by Хvt^e（G） and is called the VDE T chromatic number of G. The VDET coloring of complete bipartite graph K7,n （7 ≤ n ≤ 95） is discussed in this paper and the VDET chromatic number of K7,n （7 ≤ n ≤ 95） has been obtained.展开更多
Let Sn be the star with n vertices, and let G be any connected graph with p vertices. We denote by Eτp＋（r-1）^G（i） the graph obtained from Sr and rG by coinciding the i-th vertex of G with the vertex of degree r ...Let Sn be the star with n vertices, and let G be any connected graph with p vertices. We denote by Eτp＋（r-1）^G（i） the graph obtained from Sr and rG by coinciding the i-th vertex of G with the vertex of degree r - 1 of S,, while the i-th vertex of each component of （r - 1）G be adjacented to r - 1 vertices of degree 1 of St, respectively. By applying the properties of adjoint polynomials, We prove that factorization theorem of adjoint polynomials of kinds of graphs Eτp＋（r-1）^G（i）∪（r - 1）K1 （1 ≤i≤p）. Furthermore, we obtain structure characteristics of chromatically equivalent graphs of their complements.展开更多
Let G be a simple graph with maximum degree Δ(G) and total chromatic number x ve (G). Vizing conjectured that Δ(G) + 1 ? X ve (G) ? δ(G) + 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has...Let G be a simple graph with maximum degree Δ(G) and total chromatic number x ve (G). Vizing conjectured that Δ(G) + 1 ? X ve (G) ? δ(G) + 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs is Δ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then x ve (G) ? 8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.展开更多
Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maxim...Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maximum size of a partition of E(G) into edgecovers of G. It is known that for any graph G with minimum degree δ,δ- 1 The fractional edge covering chromatic number of a graph G, denoted by Xcf(G), is thefractional matching number of the edge covering hypergraph H of G whose vertices arethe edges of G and whose hyperedges the edge covers of G. In this paper, we studythe relation between X’c(G) and δ for any graph G, and give a new simple proof of theinequalities δ - 1 ≤ X’c(G) ≤ δ by the technique of graph coloring. For any graph G, wegive an exact formula of X’cf(G), that is,where A(G)=minand the minimum is taken over all noempty subsets S of V(G) and C[S] is the set of edgesthat have at least one end in S.展开更多
Let P（G,A） be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P（H, λ） = P（G, λ） implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.： A com...Let P（G,A） be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P（H, λ） = P（G, λ） implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.： A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175 179 （2004）], and Lau and Peng [Lau, G. C., Peng, Y. H.： Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353-376 （2009）] show that K（p - k,p - i,p） for i = 0, 1 are chromatically unique if p ≥ k ＋ 2 ≥ 4. In this paper, we show that if 2 〈 i 〈 4, the complete tripartite graph K（p - k,p - i,p） is chromatically unique for integers k ≥ i and p 〉 k2/4 ＋ i ＋ 1.展开更多
An edge coloring of hypergraph H is a function such that holds for any pair of intersecting edges . The minimum number of colors in edge colorings of H is called the chromatic index of H and is ...An edge coloring of hypergraph H is a function such that holds for any pair of intersecting edges . The minimum number of colors in edge colorings of H is called the chromatic index of H and is denoted by . Erdös, Faber and Lovász proposed a famous conjecture that holds for any loopless linear hypergraph H with n vertices. In this paper, we show that is true for gap-restricted hypergraphs. Our result extends a result of Alesandroni in 2021.展开更多
文摘In this paper, we present a new concept of the adjacent-vertex-distinguishing total coloring of graphs (briefly, AVDTC of graphs) and, meanwhile, have obtained the adjacent-vertex-distinguishing total chromatic number of some graphs such as cycle, complete graph, complete bipartite graph, fan, wheel and tree.
文摘A new concept of the D(β)-vertex-distinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger than β have different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it, is proposed in this paper. The D(2)-vertex-distinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented.
基金supported by the Defense Advanced Research Projects Agency(no.D15AP00111 and no.HR0011-17-2-0017)the Air Force Office of Scientific Research(no.FA9550-14-1-0389 and no.FA9550-16-1-0322)+2 种基金the National Science Foundation(no.ECCS-1307948)support from the NSF IGERT program(no.DGE-1069240)supported by the US Department of Energy,Office of Basic Energy Sciences(contract no.DE-SC0012704)。
文摘Metasurfaces offer a unique platform to precisely control optical wavefronts and enable the realization of flat lenses,or metalenses,which have the potential to substantially reduce the size and complexity of imaging systems and to realize new imaging modalities.However,it is a major challenge to create achromatic metalenses that produce a single focal length over a broad wavelength range because of the difficulty in simultaneously engineering phase profiles at distinct wavelengths on a single metasurface.For practical applications,there is a further challenge to create broadband achromatic metalenses that work in the transmission mode for incident light waves with any arbitrary polarization state.We developed a design methodology and created libraries of meta-units—building blocks of metasurfaces—with complex cross-sectional geometries to provide diverse phase dispersions(phase as a function of wavelength),which is crucial for creating broadband achromatic metalenses.We elucidated the fundamental limitations of achromatic metalens performance by deriving mathematical equations that govern the tradeoffs between phase dispersion and achievable lens parameters,including the lens diameter,numerical aperture(NA),and bandwidth of achromatic operation.We experimentally demonstrated several dielectric achromatic metalenses reaching the fundamental limitations.These metalenses work in the transmission mode with polarization-independent focusing efficiencies up to 50%and continuously provide a near-constant focal length over λ=1200–1650 nm.These unprecedented properties represent a major advance compared to the state of the art and a major step toward practical implementations of metalenses.
基金supported by National Natural Science Foundation of China(11761161002,61535007,61775243,61805288)Natural Science Foundation of Guangdong Province(Grant Nos.2018B030308005,2017A030310510)Science and Technology Program of Guangzhou(201804020029).
文摘Integral imaging is a promising three-dimensional(3D)imaging technique that captures and reconstructs light field information.Microlens arrays are usually used for the reconstruction process to display 3D scenes to the viewer.However,the inherent chromatic aberration of the microlens array reduces the viewing quality,and thus,broadband achromatic imaging remains a challenge for integral imaging.Here,we realize a silicon nitride metalens array in the visible region that can be used to reconstruct 3D optical scenes in the achromatic integral imaging for white light.The metalens array contains 60×60 polarization-insensitive metalenses with nearly diffraction-limited focusing.The nanoposts in each high-efficiency(measured as 47%on average)metalens are delicately designed with zero effective material dispersion and an effective achromatic refractive index distribution from 430 to 780 nm.In addition,such an achromatic metalens array is composed of only a single silicon nitride layer with an ultrathin thickness of 400 nm,making the array suitable for on-chip hybrid-CMOS integration and the parallel manipulation of optoelectronic information.We expect these findings to provide possibilities for full-color and aberration-free integral imaging,and we envision that the proposed approach may be potentially applicable in the fields of high-power microlithography,high-precision wavefront sensors,virtual/augmented reality and 3D imaging.
基金the Science and Technology Commission of Shanghai Municipality[16JC1400700]the Program of Introducing Talents of Discipline to Universities[No.111-2-04]+2 种基金the Innovative Research Team in University[IRT_16R13].C.H.thanks the Natural Science Foundation of China[No.51603037]DHU Distinguished Young Professor Program[LZB2019002]Young Elite Scientists Sponsorship Program by CAST[2017QNRC001].
文摘The research and applications of fiber materials are directly related to the daily life of social populace and the development of relevant revolutionary manufacturing industry.However,the conventional fibers and fiber products can no longer meet the requirements of automation and intellectualization in modern society,as well as people’s consumption needs in pursuit of smart,avant-grade,fashion and distinctiveness.The advanced fiber-shaped electronics with most desired designability and integration features have been explored and developed intensively during the last few years.The advanced fiber-based products such as wearable electronics and smart clothing can be employed as the second skin to enhance information exchange between humans and the external environment.In this review,the significant progress on flexible fiber-shaped multifunctional devices,including fiber-based energy harvesting devices,energy storage devices,chromatic devices,and actuators are discussed.Particularly,the fabrication procedures and application characteristics of multifunctional fiber devices such as fiber-shaped solar cells,lithium-ion batteries,actuators and electrochromic fibers are introduced in detail.Finally,we provide our perspectives on the challenges and future development of functional fiber-shaped devices.
基金the Natural Science Foundation of Gansu Province （No. 3ZS051-A25-025） the Foundation of Gansu Provincial Department of Education （No. 0501-03）.
文摘Let G = （V, E） be a simple connected graph, and ｜V（G）｜ ≥ 2. Let f be a mapping from V（G） ∪ E（G） to {1,2…, k}. If arbitary uv ∈ E（G）,f（u） ≠ f（v）,f（u） ≠ f（uv）,f（v） ≠ f（uv）; arbitary uv, uw ∈ E（G）（v ≠ w）, f（uv） ≠ f（uw）;arbitary uv ∈ E（G） and u ≠ v, C（u） ≠ C（v）, whereC（u）={f（u）}∪{f（uv）｜uv∈E（G）}.Then f is called a k-adjacent-vertex-distinguishing-proper-total coloring of the graph G（k-AVDTC of G for short）. The number min{k｜k-AVDTC of G} is called the adjacent vertex-distinguishing total chromatic number and denoted by χat（G）. In this paper we prove that if △（G） is at least a particular constant and δ ≥32√△ln△, then χat（G） ≤ △（G） ＋ 10^26 ＋ 2√△ln△.
基金The authors gratefully acknowledge the support of the National Key Research and Development Program of China(No.2017YFA0303700)the National Natural Science Foundation of China(NSFC)(No.61922038)+1 种基金the Distinguished Young Scholars Fund of Jiangsu Province(No.BK20180004)the Fundamental Research Funds for the Central Universities(No.021014380118).W.H.gratefully acknowledges the support of the Tang Scholar Program.The authors declare no conflicts of interest。
文摘Overcoming chromatic aberrations is a vital concern in imaging systems in order to facilitate fullcolor and hyperspectral imaging.By contrast,large dispersion holds opportunities for spectroscopy and tomography.Combining both functions into a single component will significantly enhance its versatility.A strategy is proposed to delicately integrate two lenses with a static resonant phase and a switchable geometric phase separately.The former is a metasurface lens with a linear phase dispersion.The latter is composed of liquid crystals(LCs)with space-variant orientations with a phase profile that is frequency independent.By this means,a broadband achromatic focusing from 0.9 to 1.4 THz is revealed.When a saturated bias is applied on LCs,the geometric phase modulation vanishes,leaving only the resonant phase of the metalens.Correspondingly,the device changes from achromatic to dispersive.Furthermore,a metadeflector with tunable dispersion is demonstrated to verify the universality of the proposed method.Our work may pave a way toward active metaoptics,promoting various imaging applications.
文摘Up to the present, there are few classes of graphs of which chromatic polynomials can be computed with formulas. For most graphs, computing their chromatic
基金Supported by the Natural Science Foundation of Gansu Province(3ZS051-A25-025)
文摘A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to v, where uv ∈E（G）. The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ＇αα（G）, is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G（V, E） is a graph with no isolated edges, then χ＇αα（G）≤32△.
基金Supported by the National Natural Science Foundation of China (Grant No.10771091)the Scientific Research Project of Northwest Normal University (Grant No.NWNU-KJCXGC-03-61)
文摘Let G be a simple graph. A total coloring f of G is called E-total-coloring if no two adjacent vertices of G receive the same color and no edge of G receives the same color as one of its endpoints. For E-total-coloring f of a graph G and any vertex u of G, let Cf （u） or C（u） denote the set of colors of vertex u and the edges incident to u. We call C（u） the color set of u. If C（u） ≠ C（v） for any two different vertices u and v of V（G）, then we say that f is a vertex-distinguishing E-total-coloring of G, or a VDET coloring of G for short. The minimum number of colors required for a VDET colorings of G is denoted by X^evt（G）, and it is called the VDET chromatic number of G. In this article, we will discuss vertex-distinguishing E-total colorings of the graphs mC3 and mC4.
基金the Science and Research Project of Education Department of Gansu Province (0501-02)
文摘Let G be a simple graph. Let f be a mapping from V（G） U E（G） to {1, 2,..., k}. Let Cf（v） = {f（v）} U {f（vw）｜w ∈ V（G）,vw ∈ E（G）} for every v ∈ V（G）. If f is a k-propertotal-coloring, and if Cf（u） ≠ Cf（v） for uv ∈ V（G）,uv E E（G）, then f is called k-adjacentvertex-distinguishing total coloring of G（k-AVDTC of G for short）. Let χat（G） = min{k｜G has a k-adjacent-vertex-distinguishing total coloring}. Then χat（G） is called the adjacent-vertex-distinguishing total chromatic number. The adjacent-vertex-distinguishing total chromatic number on the Cartesion product of path Pm and complete graph Kn is obtained.
文摘Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C（x） denote the set of colors of vertex x and of the edges incident with x, we call C（x） the color set of x. If C（u） ≠ C（v） for any two different vertices u and v of V （G）, then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by Хvt^e（G） and is called the VDE T chromatic number of G. The VDET coloring of complete bipartite graph K7,n （7 ≤ n ≤ 95） is discussed in this paper and the VDET chromatic number of K7,n （7 ≤ n ≤ 95） has been obtained.
文摘Let Sn be the star with n vertices, and let G be any connected graph with p vertices. We denote by Eτp＋（r-1）^G（i） the graph obtained from Sr and rG by coinciding the i-th vertex of G with the vertex of degree r - 1 of S,, while the i-th vertex of each component of （r - 1）G be adjacented to r - 1 vertices of degree 1 of St, respectively. By applying the properties of adjoint polynomials, We prove that factorization theorem of adjoint polynomials of kinds of graphs Eτp＋（r-1）^G（i）∪（r - 1）K1 （1 ≤i≤p）. Furthermore, we obtain structure characteristics of chromatically equivalent graphs of their complements.
基金This work was partially supported by the National Natural Science Foundation of China (Grant No. 10471131)
文摘Let G be a simple graph with maximum degree Δ(G) and total chromatic number x ve (G). Vizing conjectured that Δ(G) + 1 ? X ve (G) ? δ(G) + 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs is Δ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then x ve (G) ? 8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.
基金the National Natural Science Foundation the Doctoral Foundation of the Education Committee of China.
文摘Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maximum size of a partition of E(G) into edgecovers of G. It is known that for any graph G with minimum degree δ,δ- 1 The fractional edge covering chromatic number of a graph G, denoted by Xcf(G), is thefractional matching number of the edge covering hypergraph H of G whose vertices arethe edges of G and whose hyperedges the edge covers of G. In this paper, we studythe relation between X’c(G) and δ for any graph G, and give a new simple proof of theinequalities δ - 1 ≤ X’c(G) ≤ δ by the technique of graph coloring. For any graph G, wegive an exact formula of X’cf(G), that is,where A(G)=minand the minimum is taken over all noempty subsets S of V(G) and C[S] is the set of edgesthat have at least one end in S.
文摘Let P（G,A） be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P（H, λ） = P（G, λ） implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.： A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175 179 （2004）], and Lau and Peng [Lau, G. C., Peng, Y. H.： Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353-376 （2009）] show that K（p - k,p - i,p） for i = 0, 1 are chromatically unique if p ≥ k ＋ 2 ≥ 4. In this paper, we show that if 2 〈 i 〈 4, the complete tripartite graph K（p - k,p - i,p） is chromatically unique for integers k ≥ i and p 〉 k2/4 ＋ i ＋ 1.
文摘An edge coloring of hypergraph H is a function such that holds for any pair of intersecting edges . The minimum number of colors in edge colorings of H is called the chromatic index of H and is denoted by . Erdös, Faber and Lovász proposed a famous conjecture that holds for any loopless linear hypergraph H with n vertices. In this paper, we show that is true for gap-restricted hypergraphs. Our result extends a result of Alesandroni in 2021.
