EDGE-FACE CHROMATIC NUMBER OF 2-CONNECTED PLANE GRAPHS WITH HIGH MAXIMUM DEGREE

The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with △（G）≥｜G｜ - 2≥9 has Xef（G） = △（G）.

ON THE COMPLETE CHROMATIC NUMBER OF HALIN GRAPHS

Let G be a planar graph with δ(G)≥3, fo be a face of G. In this paper it is proved that for any Halin graph with △(G)≥6, X (G)＝△(G)+1, where △(G), Xo (G) denote the maximum degree and the complete chromatic number of G, respectively.

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.

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 .

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.

AVDTC Numbers of Generalized Halin Graphs with Maximum Degree at Least 6

In a paper by Zhang and Chen et al.（see [11]）, a conjecture was made concerning the minimum number of colors Xat（G） required in a proper total-coloring of G so that any two adjacent vertices have different color sets, where the color set of a vertex v is the set composed of the color of v and the colors incident to v. We find the exact values of Xat（G） and thus verify the conjecture when G is a Generalized Halin graph with maximum degree at least 6, A generalized Halin graph is a 2-connected plane graph G such that removing all the edges of the boundary of the exterior face of G （the degrees of the vertices in the boundary of exterior face of G are all three） gives a tree.

On the Adjacent Strong Edge Coloring of Halin Graphs

A proper k-edge coloring f of graph G(V, E) is said to be a k:-adjacent strong edge coloring of graph G(V,E) iff every uv∈E(G) satisfy f[u]≠f/[v], where f[u] = {f(uw)|uw ∈E(G)} then f is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC: and x'as(G) = min{k|k-ASEC of G} is called the adjacent strong edge chromatic number. In this paper, we study the x'as(G) of Halin graphs with △A(G)≥5.

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.

Halin图的Alon-Tarsi数

图G的Alon-Tarsi数,是指最小的k使得G存在一个最大出度不大于k-1的定向D满足G的奇支撑欧拉子图的个数不同于偶支撑欧拉子图的个数.通过分析Halin图的结构,利用Alon-Tarsi定向的方法确定了Halin图的Alon-Tarsi数.

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.

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.

Δ(G)=3时的Halin图的边面全色数

研究３正则Ｈａｌｉｎ 图的边面全色数问题，证明了《最大度Δ（ Ｈｇ） ≥７ 及Δ（ Ｈｇ）＝ ４，５ ，６ 的Ｈａｌｉｎ 图的边面全色数》一文提出的如下猜想成立：对Δ（ Ｇ） ＝ ３ 时的Ｈａｌｉｎ 图有４ ≤χｅｆ（Ｇ） ≤５ ，这里Δ（ Ｇ） 表示图Ｇ 的最大度数，χｅｆ表示图Ｇ的边面全色数。

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

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

3-正则Halin-图全色数的注(英文)

本文讨论了△（G）＝3的Halin-图的金色数Xr（G）＝4的充分条件，并提出了3－正则Halin-图Xr（G）＝5的充分必要条件的猜想，其中△（G），Xr（G）分别表示G的最大度和全色数．