Neighbor Sum Distinguishing Total Colorings Of Planar Graphs

A total [k]-coloring of a graph G is a mapping φ:V(G)∪E(G)→[k]={1,2,…, k} such that any two adjacent or incident elements in V(G) U E(G) receive different colors. Let Cφ(v) denote the set of colors of the edges incident to v and the color of v. A total [k]-coloring is called adjacent vertex distinguishing (or neighbor set distinguishing) if for each edge uv∈E(G), Cφ(u) is different from Cφ(v). The smallest k is called the adjacent vertex distinguishing total chromatic number, denoted by x"a(G). Let f(v) denote the sum of the color of a vertex v and the colors of all incident edges of v. A total [j]-neighbor sum distinguishing-coloring of G is a total [k]-coloring of G such that for each edge uv∈E(G), f(u)≠f(v). Let χ"∑(G) denote the smallest value k in such a coloring of G.Neighbor set distinguishing (adjacent vertex distinguishing) total color-ing problems have been widely studied. Recently, colorings and labellings related to sums of the colors have received much attention. The family of such problems includes e.g. vertex-coloring [k]-edge-weightings, total weight choosability, magic and antimagic labellings and the irregulaity strength. A-mong them there are the1-2-3Conjecture and1-2Conjecture. For neighbor sum distinguishing total colorings, Pilsniak and Wozniak conjectured that for any graph G with maximum degree Δ(G) it holds that X"∑(G)≤Δ(G)+3. This conjecture implies the conjecture due to Zhang et al. which states that X"a(G)≤A(G)+3. This conjecture has been proved for complete graphs cycles, bipartite graphs, and subcubic graphs. In this paper, we will consider neighbor sum distinguishing total colorings of planar graphs and K4-minor free graphs. This paper is divided into three chapters.In Chapter1, we introduce some definitions and notations in the coloring theory. We also mention some results about neighbor set distinguishing total colorings and neighbor sum distinguishing total colorings. Moreover, we list our results about neighbor sum distinguishing total colorings.In Chapter2, we mainly focus on the neighbor sum distinguishing total colorings of K4-minor free graphs. By using the structure of K4-minor free graphs and some coloring teckniques, we prove that if G is a K4-minor free graph with maximum degree Δ(G), then χ"∑{G)≤Δ(G)+3; What’s more, if Δ(G)≥4, then χ"∑(G)≤Δ(G)+2.In Chapter3, we discuss the neighbor sum distinguishing total colorings of planar graphs with high maximum degree. The main tools we use are the famous Euler formula, discharging method and some combinatorial method. We prove that if G is a planar graphs with maximum degree A(G), then χ"nsd(G)≤max{Δ(G)+3,16}.According to the definitions of neighbor sum distinguishing total color-ing and adjacent vertex distinguishing total coloring, it holds that χ"a(G)≤χ"∑(G)".So the conclusions above also hold for neighbor set distinguishing total colorings.