On The Total Coloring And The Adjacent Vertex Distinguishing Total Coloring Of Joint Graphs

The coloring problem is one of popular problems which has wide application incombinatorial analysis and practice, such as scheduling problem, storage problem andelectric-network problem etc. This article has four chapters,which mainly study totalcoloring and adjacent vertex distinguishing total coloirng of graphs.Some terminology, notation and basic results in the thesis are given in chapter 1.The total coloring of a specific joint graph is studied in chapter 2. Behzad M.posed the total coloring concept in 1965. The total chromatic number x_T(G) is theleast number of colors needed to color the vertices and edges of a graph G such thatno incident or adjacent elements(vertices or edges) receive the same color. Later,Behzad M. posed the total coloring conjecture: For every simple graph G,we havex_T(G)≤Δ(G)+2. Sánchez-Arroyo [25] showed that deciding whether x_T(G)=Δ(G)+1 is NP-complete. Nowdays the total coloring conjecture is proved for someparticular families of graphs, including complete r-partite graphs and planar graphswith maximal degree at least 8. In chapter 2, according to the structure of the jointgraph and the conception of total coloring, the total chromatic number of C_n∨K_n isobtained. Consequently, we prove the total coloring conjecture in such specific jointgraph.The adjacent vertex distinguishing total coloring of two joint graphs are studiedin both chapter 3 and chapter 4. In 2004 Zhang Zhongfu presented the concept ofadjacent vertex distinguishing total coloring whose content is: Let G be a connectedsimple graph with order at least 2, k be a positive integer and f be a mappling fromV(G)∪E(G) to {1,2,...,k}. Let C(u)={f(u)}∪{f(uv)|uv∈E(G),v∈V(G)}for all u∈V (G). If(1) for any uv, vw∈E(G),u≠w, we have f(uv)≠f(vw);(2) for any uv∈E(G), we have f(u)≠f(v), f(u)≠f(uv), f(v)≠f(uv),then f is called a k-proper total coloring of graph G. Forthermore, if f still satisfies(3) for every uv∈E(G), we have C(u)≠C(v),then f is called a k-adjacent vertex distinguishing total coloring of G (k-AVDTC forshort). The number min{k|G has a k-adjacent vertex distinguishing total coloring}is called the adjacent vertex distinguishing total chromatic number and denoted by X_at(G), where C(u) is called the color set of vertex u. In chapter 3, by using inductionand instructure method, we obtain the adjacent vertex distinguishing total chromaticnumber of W_m∨p_n. In chapter 4, also by using induction and instructure method,based on W_m∨P_n, we obtain the adjacent vertex distinguishing total chromatic num-ber of W_m∨C_n. We give the main results as follows:Theorem For the joint graph C_n∨K_n(n≥5), we have XT(C_n∨K_n)=△+1.Theorem For the joint graph W_m∨P_n(m≥3),we haveTheorem For the joint graph W_m∨C_n(m≥3, n≥3), we have...