The Equitable Total Chromatic Number of Some Join graphs

A proper total-coloring of graph G is said to be?equitable if the number of elements (vertices and edges) in any?two color classes differ by at most one, which the required?minimum number of colors is called the equitable total chromatic?number. In this paper, we prove some theorems on equitable?total coloring and derive the equitable total chromatic numbers?of Pm V?Sn, Pm V?Fn and Pm V Wn.

Total Chromatic Number of the Join of K_(m,n) and C_n

The total chromatic number xT（G） of a graph G is the minimum number of colors needed to color the elements（vertices and edges） of G such that no adjacent or incident pair of elements receive the same color, G is called Type 1 if xT（G） =△（G）＋1. In this paper we prove that the join of a complete bipartite graph Km,n and a cycle Cn is of Type 1.

On total chromatic number of planar graphs without 4-cycles

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.

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.

Adjacent-Vertex-Distinguishing Total Chromatic Number of P_m×K_n

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.

THE TOTAL CHROMATIC NUMBER OF PSEUDO-OUTERPLANAR GRAPHS

A planar graph G is called a i pseudo outerplanar graph if there is a subset V 0V(G),|V 0|=i, such that G-V 0 is an outerplanar graph. In particular, when G-V 0 is a forest, G is called a i pseudo tree. In this paper, the following results are proved: (i) The conjecture on the total coloring is true for all 1 pseudo outerplanar graphs; (ii) χ t(G)=Δ(G)+1 for any 1 pseudo outerplanar graph G with Δ(G)6 and for any 1 pseudo tree G with Δ(G)3, where χ t(G) is the total chromatic number of a graph G .

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.

ON THE TOTAL COLORING OF GRAPH G ∨H

The total chromatic number XT(G) of graph G is the least number of colorsassigned to VE(G) such that no adjacent or incident elements receive the same color.Gived graphs G1,G2, the join of G1 and G2, denoted by G1∨G2, is a graph G, V(G) =V(GI)∪V(G2) and E(G) = E(G1)∪E(G2) ∪{uv | u∈(G1), v ∈ V(G2)}. In this paper, it's proved that if v(G) = v(H), both Gc and Hc contain perfect matching and one of the followings holds: (i)Δ(G) =Δ(H) and there exist edge e∈ E(G), e' E E(H)such that both G-e and H-e' are of Class l; (ii)Δ(G)<Δ(H) and there exixst an edge e ∈E(H) such that H-e is of Class 1, then, the total coloring conjecture is true for graph G ∨H.

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.

Further Results on Acyclic Chromatic Number

An acyclic coloring of a graph is a proper vertex coloring such that the union of any two color classes induces a disjoint collection of trees.The purpose of this paper is to derive exact values of acyclic chromatic number of some graphs.

Vertex-distinguishing Total Colorings of 2Cn

Let f be a proper total k-coloring of a simple graph G. For any vertex x ∈ V（G）, let Cf（x） denote the set of colors assigned to vertex x and the edges incident with x. If Cf（u） ≠ Cf（v） for all distinct vertices u and v of V（G）, then f is called a vertex- distinguishing total k-coloring of G. The minimum number k for which there exists a vertex- distinguishing total k-coloring of G is called the vertex-distinguishing total chromatic number of G and denoted by Xvt（G）. The vertex-disjoint union of two cycles of length n is denoted by 2Cn. We will obtain Xvt（2Cn） in this paper.

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.

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.

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

用结构分析法完整刻画单圈图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的仙人掌图成立.

完全二部图K_(4,n)的点被多重集可区别的E-全染色

利用反证法、色集合事先分配法及构造具体染色等方法,讨论完全二部图K_(4,n)的点被多重集可区别的E-全染色,并确定K_(4,n)的点被多重集可区别的E-全色数.

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

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

关于C_m×C_(5n)的全色数和邻强边色数

设G是一个简单图,k为正整数,V(G)∪E(G)到{1,2,…,k}的一个映射f满足:对于任意的uv∈E(G)有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);任意的uv,vw∈E(G),u≠w,有f(uv)≠f(uw),则称f为G的k-全染色,简记为k-TC,并称ΧT(G)=min{k|G存在k-TC}为G的全色数.证明了圈Cm与圈C5n的笛卡尔积图的全色数和邻强边色数都为5.