Strict Neighbor-distinguishing Total Coloring And Strong Edge-coloring Of Graphs

A proper k-total-coloring of a graph G is a mapping ?:V(G)?E{G)?{1,2,…,k},such that any two adjacent or incident elements in V(G)? E(G)receive different colors.Let C?[v]={?(v)} ?{?(uv)|uv ? E(G)} be the set of colors assigned to a vertex v and those edges incident to v.? is strict neighbor-distinguishing if |C?[u]\C?[v]|? 1 and |C?[v]\C?[u]|? 1 for each edge uv ? E(G).The strict neighbor-distinguishing total index,denoted by xsnt(G),of G is the minimum integer k such that G has a k-strictly neighbor-distinguishing total coloring.A proper k-edge-coloring of a graph G is a mapping ?:E{G)?{1,2,…,k} such that ?(c1)??(c2)for any two adjacent edges c1 and c2 in E{G).The chromatic index?'(G)of G is the minimum integer k such that G is proper k-edge-colorable.A proper k-edge-coloring ? of G is called a strong k-edge-coloring if any two edges at distance at most two get distinct colors.The strong chromatic index,denoted by ?'s(G),of G is the minimum integer k such that G is strongly k-edge-colorable.By the definitions,it is straightforward to see that ?'s(G)? ?'(G)??.The dissertation consists of three chapters as follows.In Chapter 1,we collect some basic notation and give a detailed survey on the related fields.In Chapter 2,we focus on the strict neighbor-distinguishing total coloring of graphs.We prove that every graph G with ??3 has ?snt(G)?6,every graph G with ??4 has?snt(G)? 8,Moreover,It is shown that every Halin graph or 2-connected outerplanar graph G has ?snt(G)=?+2.In Chapter 3,the strong edge coloring of two special graphs are investigated.We show that every K4-minor free graph G with ?? 4 and without adjacent ?-vertices satisfies ?'s?3?-3,and every graph G with ?=5 and without adjacent 5-vertices satisfies ?'s?31.