Neighbor sum distinguishing total chromatic number of K4-minor free graph

A k-total coloring of a graph G is a mapping φ： V（G） U E（G） → {1, 2,..., k} such that no two adjacent or incident elements in V（G） U E（G） receive the same color. Let f（v） denote the sum of the color on the vertex v and the colors on all edges incident with v. We say that ~ is a k-neighbor sum distinguishing total coloring of G if f（u） ≠ f（v） for each edge uv C E（G）. Denote X＂ （G） the smallest value k in such a coloring of G. Pilgniak and Wo/niak conjectured that for any simple graph with maximum degree △（G）, X＂（G） ≤ 3. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that for Ka-minor free graph G with △（G） ≥ 5, X＂（G） = △（G） ＋ 1 if G contains no two adjacent A-vertices, otherwise, X＂（G） = △（G） ＋ 2.

Vertex-distinguishing E-total Coloring of Complete Bipartite Graph K 7,n when7≤n≤95

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.

Vertex-distinguishing IE-total Colorings of Cycles and Wheels

Let G be a simple graph. An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C（u） be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C（u）=C（v） for any two different vertices u and v of V （G）, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt（G）, and is called the VDIET chromatic number of G. We get the VDIET chromatic numbers of cycles and wheels, and propose related conjectures in this paper.

Vertex-distinguishing VE-total Colorings of Cycles and Complete Graphs

Let G be a simple graph of order at least 2.A VE-total-coloring using k colors of a graph G is a mapping f from V (G) E(G) into {1,2,···,k} such that no edge receives the same color as one of its endpoints.Let C(u)={f(u)} {f(uv) | uv ∈ E(G)} be the color-set of u.If C(u)=C(v) for any two vertices u and v of V (G),then f is called a k-vertex-distinguishing VE-total coloring of G or a k-VDVET coloring of G for short.The minimum number of colors required for a VDVET coloring of G is denoted by χ ve vt (G) and it is called the VDVET chromatic number of G.In this paper we get cycle C n,path P n and complete graph K n of their VDVET chromatic numbers and propose a related conjecture.

Adjacent Vertex-distinguishing E-total Coloring on Some Join Graphs Cm V Gn

Let G(V, E) be a simple connected graph and k be positive integers. A mapping f from V∪E to {1, 2, ··· , k} is called an adjacent vertex-distinguishing E-total coloring of G(abbreviated to k-AVDETC), if for uv ∈ E(G), we have f(u) ≠ f(v), f(u) ≠ f(uv), f(v) ≠ f(uv), C(u) ≠C(v), where C(u) = {f(u)}∪{f(uv)|uv ∈ E(G)}. The least number of k colors required for which G admits a k-coloring is called the adjacent vertex-distinguishing E-total chromatic number of G is denoted by x^e_(at) (G). In this paper, the adjacent vertexdistinguishing E-total colorings of some join graphs C_m∨G_n are obtained, where G_n is one of a star S_n , a fan F_n , a wheel W_n and a complete graph K_n . As a consequence, the adjacent vertex-distinguishing E-total chromatic numbers of C_m∨G_n are confirmed.

Vertex-distinguishing IE-total Colorings of Complete Bipartite Graphs K8,n

Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χ_(vt)^(ie) (G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K_(8,n)are discussed in this paper. Particularly, the VDIET chromatic number of K_(8,n) are obtained.

Algorithm on the Optimal Vertex-Distinguishing Total Coloring of mC9

Let G be a simple graph and f be a proper total coloring(or a total coloring in brief) of G. For any vertex u in G, Cf(u) denote the set of colors of vertex u and edges which incident with vertex u. Cf(u) is said to be the color set of vertex u under f. If Cf(u) = Cf(v)for any two distinct vertices u and v of G, then f is called vertex-distinguishing total coloring of G(in brief VDTC), a vertex distinguishing total coloring using k colors is called k-vertexdistinguishing total coloring of G(in brief k-VDTC). The minimum number k for which there exists a k-vertex-distinguishing total coloring of G is called the vertex-distinguishing total chromatic number of G, denoted by χvt(G). By the method of prior distributing the color sets, we obtain vertex-distinguishing total chromatic number of m C9 in this paper.

Neighbor Sum Distinguishing Total Choosability of Planar Graphs with Maximum Degree at Least 10

A neighbor sum distinguishing(NSD)total coloringφof G is a proper total coloring of G such thatΣz∈EG(u)U{u}φ(z)≠Σz∈EG(v)U{v}φ(z)for each edge uv∈E(G),where EG(u)is the set of edges incident with a vertex u.In 2015,Pilśniak and Wozniak conjectured that every graph with maximum degreeΔhas an NSD total(Δ+3)-coloring.Recently,Yang et al.proved that the conjecture holds for planar graphs withΔ≥10,and Qu et al.proved that the list version of the conjecture also holds for planar graphs withΔ≥13.In this paper,we improve their results and prove that the list version of the conjecture holds for planar graphs withΔ≥10.

Neighbor Sum Distinguishing Total Choice Number of Planar Graphs without 6-cycles

Pilsniak and Wozniak put forward the concept of neighbor sum distinguishing(NSD)total coloring and conjectured that any graph with maximum degreeΔadmits an NSD total(Δ+3)-coloring in 2015.In 2016,Qu et al.showed that the list version of the conjecture holds for any planar graph withΔ≥13.In this paper,we prove that any planar graph withΔ≥7 but without 6-cycles satisfies the list version of the conjecture.

Neighbor Sum Distinguishing Total Colorings of Graphs with Bounded Maximum Average Degree

A proper [h]-total coloring c of a graph G is a proper total coloring c of G using colors of the set [h] ={1, 2,..., h}. Let w（u） denote the sum of the color on a vertex u and colors on all the edges incident to u. For each edge uv ∈ E（G）, if w（u） ≠ w（v）, then we say the coloring c distinguishes adjacent vertices by sum and call it a neighbor sum distinguishing [h]-total coloring of G. By tndi∑ （G）, we denote the smallest value h in such a coloring of G. In this paper, we obtain that G is a graph with at least two vertices, if mad（G） 〈 3, then tndi∑ （G） ≤k ＋ 2 where k = max{△（G）, 5}. It partially confirms the conjecture proposed by Pilgniak and Wolniak.

An Upper Bound for the Adjacent Vertex-Distinguishing Total Chromatic Number of a Graph

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△.

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.

Vertex Distinguishing Equitable Total Chromatic Number of Join Graph

A vertex distinguishing equitable total coloring of graph G is a proper total coloring of graph G such that any two distinct vertices＇ coloring sets are not identical and the difference of the elements colored by any two colors is not more than 1. In this paper we shall give vertex distinguishing equitable total chromatic number of join graphs Pn VPn, Cn VCn and prove that they satisfy conjecture 3, namely, the chromatic numbers of vertex distinguishing total and vertex distinguishing equitable total are the same for join graphs Pn V Pn and Cn ∨ Cn.

Neighbor Sum Distinguishing Total Coloring of Triangle Free IC-planar Graphs

A graph is IC-planar if it admits a drawing in the plane such that each edge is crossed at most once and two crossed edges share no common end-vertex.A proper total-k-coloring of G is called neighbor sum distinguishing if∑_c(u)≠∑_c(v)for each edge uv∈E(G),where∑_c(v)denote the sum of the color of a vertex v and the colors of edges incident with v.The least number k needed for such a total coloring of G,denoted byχ∑"is the neighbor sum distinguishing total chromatic number.Pilsniak and Wozniak conjecturedχ∑"(G)≤Δ(G)+3 for any simple graph with maximum degreeΔ(G).By using the famous Combinatorial Nullstellensatz,we prove that above conjecture holds for any triangle free IC-planar graph with△(G)≥7.Moreover,it holds for any triangle free planar graph withΔ(G)≥6.

Neighbor Sum Distinguishing Total Colorings of Triangle Free Planar Graphs

A total k-coloring c of a graph G is a proper total coloring c of G using colors of the set [k] = {1, 2,...,k}. Let f（u） denote the sum of the color on a vertex u and colors on all the edges incident to u. A k-neighbor sum distinguishing total coloring of G is a total k-coloring of G such that for each edge uv ∈ E（G）, f（u） ≠ f（v）. By X＂nsd（G）, we denote the smallest value k in such a coloring of G. Pilgniak and Wozniak conjectured that X＂nsd（G） ≤ △（G）＋ 3 for any simple graph with maximum degree △（G）. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that the conjecture holds for any triangle free planar graph with maximum degree at least 7.

Neighbor Distinguishing Total Choice Number of Sparse Graphs via the Combinatorial Nullstellensatz

Let G =（V, E） be a graph and Ф ： V tA E → {1, 2,..., k） be a total-k-coloring of G. Let f（v）（S（v）） denote the sum（set） of the color of vertex v and the colors of the edges incident with v. The total coloring Ф is called neighbor sum distinguishing if （f（u） ≠ f（v）） for each edge uv∈ E（G）. We say that Фis neighbor set distinguishing or adjacent vertex distinguishing if S（u） ≠ S（v） for each edge uv ∈ E（G）. For both problems, we have conjectures that such colorings exist for any graph G if k 〉 △（G） ＋ 3. The maximum average degree of G is the maximum of the average degree of its non-empty subgraphs, which is denoted by mad （G）. In this paper, by using the Combinatorial Nullstellensatz and the discharging method, we prove that these two conjectures hold for sparse graphs in their list versions. More precisely, we prove that every graph G with maximum degree A（G） and maximum average degree mad（G） has ch＇＇∑（G） 〈 △（G） ＋ 3 （where ch＇＇∑（G） is the neighbor sum distinguishing total choice number of G） if there exists a pair （k, m） ∈ {（6, 4）, （5, 18/5）, （4, 16）} such that △（G） 〉 k and mad （G） 〈 m.

A Note on Adjacent-Vertex-Distinguishing Total Chromatic Numbers for P_m × P_n,P_m × C_n and C_m × C_n

Let G be a simple graph. Let f be a mapping from V (G) ∪ E(G) to {1,2,...,k}. Let Cf(v) = {f(v)} ∪ {f(vw)|w ∈ V (G),vw ∈ E(G)} for every v ∈ V (G). If f is a k-proper- total-coloring, and for u,v ∈ V (G),uv ∈ E(G), we have Cf(u) = Cf(v), then f is called a k- adjacent-vertex-distinguishing total coloring (k-AV DTC for short). Let χat(G) = min{k|G have a k-adjacent-vertex-distinguishing total coloring}. Then χat(G) is called the adjacent-vertex- distinguishing total chromatic number (AV DTC number for short)...

单圈图的邻点全和可区别全染色

用结构分析法完整刻画单圈图U的邻点全和可区别全染色,并得到当U■C_(n)且n■0(mod 3)时,ftndiΣ(U)=Δ(U)+2;其他情况下,ftndiΣ(U)=Δ(U)+1.表明邻点全和可区别全染色猜想在任意单圈图上都成立.

一类仙人掌图的D(2)-点可区别全染色

用数学归纳法和组合分析法给出最大度为3的仙人掌图G T的D(2)-点可区别全染色,进而得到χ_(2vt)(G T)≤6.结果表明,D(β)-VDTC猜想对最大度为3的仙人掌图成立.

三正则构造图的邻点全和可区别全染色

首先,根据Snark图的结构特点,构造基于双星和十字交叉形的两类三正则图;其次,利用穷染法和组合分析法研究四类三正则构造图的邻点全和可区别全染色问题,得到了它们的邻点全和可区别全色数均为2.