On the Maximum Number of Dominating Classes in Graph Coloring

We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result allows us to construct classes of graphs such that and thus provide some information regarding two questions raised in [1] and [2].

Quark-Antiquark and Diquark Condensates in Vacuum in Two-Flavor Four-Fermion Interaction Models with Any Color Number N_c

The color number Nc-dependence of the interplay between quark-antiquark condensates （q^-q） and diquark condensates （qq） in vacuum in two-flavor four-fermion interaction models is researched. The results show that the Gs-Hs （the coupling constant of scalar （q^-q）2-scalar （qq）2 channel） phase diagrams will be qualitatively consistent with the case of Nc = 3 as Nc varies in 4D Nambu-Jona-Lasinio model and 219 Gross Neveu （GN） model, However, in 3D GN model, the behavior of the Gs-Hp （the coupling constant of pseudoscalar （qq）^2 channel） phase diagram will obviously depend on No. The known characteristic that a 3D GN model does not have the coexistence phase of the condensates （q^-q） and （qq） is proven to appear only in the case of Nc ≤ 4. In all the models, the regions occupied by the phases containing the diquark condensates （qq） in corresponding phase diagrams will gradually decrease as Nc grows up and finally go to zero if Nc → ∞, i.e. in this limit only the pure （q^-q） phase could exist.

Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz

Let G=(V,E)be a graph andφbe a total coloring of G by using the color set{1,2,...,k}.Let f(v)denote the sum of the color of the vertex v and the colors of all incident edges of v.We say thatφis neighbor sum distinguishing if for each edge uv∈E(G),f(u)=f(v).The smallest number k is called the neighbor sum distinguishing total chromatic number,denoted byχ′′nsd(G).Pil′sniak and Wo′zniak conjectured that for any graph G with at least two vertices,χ′′nsd(G)(G)+3.In this paper,by using the famous Combinatorial Nullstellensatz,we show thatχ′′nsd(G)2(G)+col(G)-1,where col(G)is the coloring number of G.Moreover,we prove this assertion in its list version.

Bounds for the Rainbow Disconnection Numbers of Graphs

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.