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.

Adjacent Vertex Distinguishing Total Coloring of M（Tn）

A k-proper total coloring of G is called adjacent distinguishing if for any two adjacent vertices have different color sets. According to the property of trees, the adjacent vertex distinguishing total chromatic number will be determined for the Mycielski graphs of trees using the method of induction.

Adjacent vertex-distinguishing total colorings of K_s∨K_t

Let G be a simple graph and f be a proper total kcoloring of G. The color set of each vertex v of G is the set of colors appearing on v and the edges incident to v. The coloring f is said to be an adjacent vertex-distinguishing total coloring if the color sets of any two adjacent vertices are distinct. The minimum k for which such a coloring of G exists is called the adjacent vertex-distinguishing total chromatic number of G. The join graph of two vertex-disjoint graphs is the graph union of these two graphs together with all the edges that connect the vertices of one graph with the vertices of the other. The adjacent vertex-distinguishing total chromatic numbers of the join graphs of an empty graph of order s and a complete graph of order t are determined.

On the Vertex Strong Total Coloring of Halin-Graphs

A proper k-total coloring f of the graph G（V, E） is said to be a k-vertex strong total coloring if and only if for every v ∈ V（G）, the elements in N[v] are colored with different colors, where N[v] =. {u｜uv E V（G）} ∪{v}. The value xT^vs（G） = min{k｜ there is a k-vertex strong total coloring of G} is called the vertex strong total chromatic number of G. For a 3-connected plane graph G（V, E）, if the graph obtained from G（V, E） by deleting all the edges on the boundary of a face f0 is a tree, then G（V, E） is called a Halin-graph. In this paper, xT^vs,8（G） of the Halin-graph G（V,E） with A（G） 〉 6 and some special graphs are obtained. Furthermore, a conjecture is initialized as follows： Let G（V, E） be a graph with the order of each component are at least 6, then xT^vs（G） ≤ △（G） ＋ 2, where A（G） is the maximum degree of G.

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.

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.

On the adjacent-vertex-strongly-distinguishing total coloring of graphs

For any vertex u ? V(G), let T N (u) = {u} ∪ {uυ|uυ ? E(G), υ ? υ(G)} ∪ {υ ? υ(G)|uυ ? E(G) and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C f(u) = {f(x) | x ? T N (u)}. For any two adjacent vertices x and y of V(G) such that C f(x) ≠ C f(y), we refer to f as a k-avsdt-coloring of G (“avsdt” is the abbreviation of “ adjacent-vertex-strongly-distinguishing total”). The avsdt-coloring number of G, denoted by χast(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We prove Δ(G) + 1 ? χast(G) ? Δ(G) + 2 for any tree or unique cycle graph G.

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that X as ′ (G) = X t (G) for every k-regular graph G with no C 5 component (k ? 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V(G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.

Total colorings of planar graphs with maximum degree at least 8

Planar graphs with maximum degree Δ 8 and without 5- or 6-cycles with chords are proved to be (Δ + 1)-totally-colorable.

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.

Equitable Total Coloring of F_n ∨ W_n

The minimum number of total independent partition sets of V ∪ E of graph G（V,E） is called the total chromatic number of G denoted by χt（G）. If the difference of the numbers of any two total independent partition sets of V ∪ E is no more than one＇, then the minimum number of total independent partition sets of V ∪ E is called the equitable total chromatic number of G, denoted by χet（G）. In this paper, we obtain the equitable total chromatic number of the join graph of fan and wheel with the same order.

A Note on the Minimum Total Coloring of Planar Graphs

Graph coloring is an important tool in the study of optimization, computer science, network design, e.g., file transferring in a computer network, pattern matching, computation of Hessians matrix and so on. In this paper, we consider one important coloring, vertex coloring of a total graph, which is also called total coloring. We consider a planar graph G with maximum degree △（G） 〉 8, and proved that if G contains no adjacent i,j-cycles with two chords for some i,j E {5,6,7}, then G is total-（△ ＋ 1）-colorable.

Acyclic Total Colorings of Planar Graphs without l Cycles

A proper total coloring of a graph G such that there are at least 4 colors on those vertices and edges incident with a cycle of G, is called acyclic total coloring. The acyclic total chromatic number of G is the least number of colors in an acyclic total coloring of G. In this paper, it is proved that the acyclic total chromatic number of a planar graph G of maximum degree at least k and without 1 cycles is at most △（G） ＋ 2 if （k, l） ∈ {（6, 3）, （7, 4）, （6, 5）, （7, 6）}.

List Total Colorings of Planar Graphs without Triangles at Small Distance

Suppose that G is a planar graph with maximum degree △. In this paper it is proved that G is total-（△ ＋ 2）-choosable if （1） △ ≥ 7 and G has no adjacent triangles （i.e., no two triangles are incident with a common edge）; or （2） △ ≥6 and G has no intersecting triangles （i.e., no two triangles are incident with a common vertex）; or （3） △ ≥ 5, G has no adjacent triangles and G has no k-cycles for some integer k ∈ {5, 6}.

Total Coloring of Planar Graphs without Chordal 7-cycles

A k-total-coloring of a graph G is a coloring of vertices and edges of G using k colors such that no two adjacent or incident elements receive the same color.In this paper,it is proved that if G is a planar graph with Δ（G） ≥ 7 and without chordal 7-cycles,then G has a（Δ（G） ＋ 1）-total-coloring.

On Total Colorings of Some Special 1-planar Graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, we verify the total coloring conjecture for every 1-planar graph G if either △（G） ≥9 and g（G）≥ 4, or △（G） ≥ 7 and g（G）≥5, where △（G） is the maximum degree of G and g（G） is the girth of G.

Total Coloring of G×P_n and G×C_n

It is proved that if G is a (+1)-colorable graph, so are the graphs G×Pn and C×Cn, where Pn and Cn are respectively the path and cycle with n vertices, and the maximum edge degree of the graph. The exact chromatic numbers of the product graphs and are also presented. Thus the total coloring conjecture is proved to be true for many other graphs.

Equitable Total Coloring of Some Join Graphs

The total chromatic number χt(G) of a graph G(V,E) is the minimum number of total independent partition sets of V E, satisfying that any two sets have no common element. If the difference of the numbers of any two total independent partition sets of V E is no more than one, then the minimum number of total independent partition sets of V E is called the equitable total chromatic number of G, denoted by χet(G). In this paper, we have obtained the equitable total chromatic number of Wm Kn, Fm Kn and Sm Kn whi...

A Note on List Edge and List Total Coloring of Planar Graphs without Adjacent Short Cycles

LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl（G）=Δand the list total chromatic numberχl（G）=Δ＋1.

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.