The Adjacent Vertex-distinguish Total Coloring And The Coloring Problem That Be Submitted To The Total Colors' Subgraph

The coloring problem is one of primary fields in the study of graph theories.Itis from the study of the celebrated four color problem.With the application ofthe coloring problem some scholars presented and studied a few coloring problemwith different restriction.A (proper)k-coloring of graph G is an assignment of one of k colors to each ver-tex in such a way that adjacent vertices have distinct colors.Define the chromaticnumber of G as x(G)=min{k|graph G has k-colorings}.Similar,a (proper)k-edge-coloring of graph G is an assignment of one of k colors to each edge so that notwo adjacent edges have the same color.The edge-chromatic number is defined asx′(G)=min{k|graph G has k-edge-colorings}.The total coloring is a generalization of the coloring and the edge coloring.It'sa traditional coloring problem and was introduced by Vizing(1964) and indepen-dently Behzad(1965).The tltal coloring is defined as all of vertices and edges ofthe graph are colored in such a way that no two adjacent or incident elements arecolored the same.The total chromatic number is defined as x_T(G)=min{k|G hask-TC}.On the basis of the total coloring, Zhang Zhongfu presented the conceptof the adjacent vertex-distinguishing total colorings and gave the conjecture andtwo results.The definition of asjacent vertex-distinguishing total coloring by Zhang Zhongfuis as follows: Let G(V(G), E(G)) is a simple connected graph of which the or-der at least 2,k is a positive integer and f is a mapping from V(G)∪E(G) to {1,2,…,k}.For any u∈V(G),if1)for any uv,vw∈E(G),u≠w,there is f(uv)≠f(vw).2)for any uv∈E(G),there are f(u)≠f(v), f(u)≠f(uv), f(uv)≠f(v).Then f is called a k-total coloring of graph G and the total-chromatic number isdefined as x_T(G)(or denoted as x″(G))=min{k|graph G has k-total-colorings}.Iff also satisfics3)for any uv∈E(G),there is C(u)≠C(v);where C(u)={f(u)}∪{f(uv)|uv∈E(G)} is called the color set of vertex u .Then f is called a k adjacent vertex-distinguishing total coloring of graph G(brieflynoted as k-AVDTC) and x_at(G)=min{k|G has k-AVDTC} is called the adjacentvertex-distinguishing total chromatic number of graph G.Zhang Zhongfu presented two importent results about the adjacent vertex-distinguishing total coloring.For any simple connected graph G of order n(n≥2),adjacent vertex-distinguish-ing total chromatic number x_at(G) exsits,andx_at(G)≥△(G)+1.If G(V(G), E(G)) has two adjacent maximum degree vertices,then x_at(G)≥△(G)+2.The two results about the adjacent vertex-distinguishing total coloring areright apparently.The following conjecture is proposed by Zhang Zhongfu.For any simple connected graph G of order n(n≥2),then x_at(G)≤△(G)+3.The problem of determining the adjacent vertex-distinguishing total chro-matic number of a graph is NP-hard. In present, we obtain the adjacent vertex- distinguishing total chromatic number for special graphs such as path,cycle,completegraph,2-complete graph,star, fan,wheel,tree etc.We also obtain the adjacent vertex-distinguishing total chromatic number for the Mycielski graph,link graph,the Carte-sian product graph,Petersen graph,Heawood graph,Thomassen graph erc.The edge-coloring problem was pised in 1880 in relation with the well-knownfour-color conjecture. In 1964,Vizing proved the famous Vizing's theorem:â–³(G)≤x′(G)≤△(G)+1 for any simple graph G.In 1974,R.P.Gupta studied the edge cover coloring problem.The edge covercoloring of a graph G is to color all the edges of G so that each color appears ateach vertex v at least once.The maximum positive integer k such that G has ak-edge cover-coloring is called the edge cover chromatic index of G and is denotedby x′_c(G).A graph G is said to be of Type CI if x′_c(G)=δand of Type Câ…¡ifx′_c(G)=δ-1.G.Liu,L.Miao and H.Song studied the edge cover coloring problemsand got many results.In 2006,L.Sun prosed the concept of the total colors maximal cliques (vertex-)coloring.A total colors maximal cliques coloring of graph G is a vertex-coloringsuch that all colors appear at each maximal clique of graph G.The maximumnumber of total colors maximal cliques coloring of G is called total colors maxi-mal cliques chromatic number and denoted by x_maxcT(G).Apparently,x_maxcT(G)≤min{|H||H is a maximal clique of graph G}.In this thesis,the first part deals with the adjacent vertex-distinguishing to-tal chromatic number for Hajós sum of wheel,complete graph and we obtainthe adjacent vertex-distinguishing total chromatic number for graph P_n^k, flowerG.The second part focuses on the equivalence of total colors maximal cliques chro-matic number of the Lexicographic product,the Caretsian product of graph,linkgraph,the outer graph, graph K_n-N,graph (?)_n, Mycielski graph,similar Mycielskigraph.We briefly summerize our main results as follow: Let G₁ and G₂ be vertex disjoint graphs,containing edges x₁y₁∈E(G₁) andx₁y₂∈E(G₂). The Hajós sum G=(G₁,x₁y₁) (G₂,x₂y₂) of the pairs(G₁, x₁y₁) and (G₂, x₂y₂) is obtained from G₁∪G₂ by identifying x₁ and x₂,deletingthe edge x₁y₁, x₂y₂,and adding the edge y₁y₂.Let W_n=K₁∨C_n, V(W_n)={v₁, v₂,..., v_n, V₀}, E(W_n)={v_iv_i+1|i=1, 2,...,n; v_n+1=v₁}∪{v₀v_i[i=1, 2,..., n}, W'_n is the copy of W_n.Theorem 2.1.1 Hajós sum W^*_n=(W_n, v₁v₂)+(W'_n, v'₁v'₂) identifies v₁ andv'₁ as v₁, thenTheorem 2.1.2 Hajōs sum G=(W_n, v₀v₁)+(W'_n,v'₀v'₁) identifies v₀ andv'₀ as v₀, then Xat(G)=2n-1.Theorem 2.1.3 Hajòs sum G=(K_m,v₁v₂)+(K_n, v'₁v'₂) identifies v₁ andv'₁ as v₁, thenGraph P_n is a path which the order is n.Graph P^k_n is obtained from addingan edge to graph P_n if and only if the distance of two vertices is k.Theorem 2.2.1 For graph P^k_n,k=「n/2」,there is Xat(P^k_n)=5.Graph K_n is a complete graph which the vertices is v₁, v₂,..., v_n.Flower G isobtained from adding the vertices v_i1, v_i2,..., v_im, to the vertice v_i of K_n, linkingthe vertices v_i1, v_i2,..., v_imi, to the path v_i1v_i2..., v_imi.Theorem 2.2.2 For flower G,let m_s=max_k=1,2,...,n m_k,then For any graph G,it's line graph L(G) is defined as:vertex set is E(G),thereis an edge in two vertices of graph L(G) if and only if two edges are adjacent ingraph G.For any graph G,it's total graph T(G) is defined as:vertex set is V(G)∪E(G),there is an edge in two elements of graph T(G) if and only if two elementsare adjacent or incident in graph G.Let p=min{|G'||G' is a maximal clique of graph G}, q=min{[H'||H' is amaximal clique of graph H}.Theorem 3.1.1 If graph G is the line graph of H and p≥4,then the to-tal colors maximal cliques coloring of G and the edge covered coloring of H areequivalent.Corollary 3.1.2 Gupta's theorem is equivalent to two cases as follow:(1) If G is the line graph of H and p≥4,then p-1≤XmaxcT(G)≤P.(2) If G is the total graph of H and p≥4,then p-1≤XmaxcT(G)≤P.M is the match of the complete graph K_n,then all maximal cliques' numberof K_n-M is same and is n-2|M|+|M|=n-|M|.The vertex set of any maxi-mal clique of K_n-M is the union of V(K_n)\V(M) and the vertices which areobtained from the match edges of M.Theorem 3.1.3 For the complete graph K_n, N(?)E(K_n) andδ(K_n-N)≥n-2,then XmaxcT(K_n-N)=n-|N|.Theorem 3.1.4 If G=(?)_n,thenThe link graph G∨H of graph G and graph H is defined as follow: V(G∨H)=V(G)∪V(H), E(G∨H)=E(G)∪E(H)∪{uv|u∈V(G), v∈V(H)}. Theorem 3.1.5 For any simple connected graph G,H,then XmaxcT(G∨H)=XmaxcT(G)+XmaxcT(H).The Lexicographic product graph G[H] of graph G and graph H is definedto be a graph with V(G[H])=V(G)×V(H) and E(G[H])={(a,x)(b,y)|ab∈E(G) or a=b and xy∈E(H)}.Theorem 3.1.6 If graph G,H satisfy XmaxcT(G)=p, XmaxcT(H)=q, thenXmax(?)T(G[H])=XmaxcT(G)XmaxcT(H).Not all graph G, H satisfies XmaxcT(G[H])=XmaxcT(G)XmaxcT(H).For example: G=P_n, H=C_2m+1, but XmaxcT(G[H])=3≠2×1.For graphs G₁=(V₁, E₁) and G₂=(V₂, E₂),the Cartesian product graphG₁×G₂] has vertex set V₁×V₂ and in which (v₁, u₁) is adjacent to (v₂, u₂) if andonly if either v₁v₂∈E₁ and u₁=u₂∈V₂ or v₁=v₂∈V₁ and u₁u₂∈E₂.Theorem 3.1.7 If p-1≤XmaxcT(G)≤p, q-1≤XmaxcT(H)≤q, thenXmaxcT(G×H)=min{XmaxcT(G). XmaxcT(H)}.We call the graph obtained by the Mycielski Construction the Mycielskigraph. Given a graph G with V(G)={v₁, v₂,..., v_n},the Mycielski graph (de-noted by M(G)) of G is defined to be a graph with V(M(G))=V∪{v'₁, v'₂,..., v'_n,ω} and E(M(G))=E(G)∪{v_iv'_j[v_iv_j∈E(G),i,j=1,..., n}∪{v'_iω|i=1,..., n}.Theorem 3.2.1 For any simple connected graph G,there is XmaxcT(M(G))=1.Theorem 3.2.2 For any simple connected graph G, let u(G)=M(G)-ω.there is XmaxcT(u(G))=XmaxcT(G).Given a graph G with V(G)={v₁, v₂,..., v_n}, the similar Mycielski graph (denoted by S(G)) of G is defined to be a graph with V(S(G))=V(G)∪V(G')∪{w},G'is the copy of graph G and E(S(G))=E(G)∪E(G')∪{v_iv'_i|v_i∈V(G),i=1.2,..., n}∪{v_iv'_j|v_iv_j∈E(G),i,j=1,2,...,n}∪{v'_iw|i=1.2,..., n}.Graph S_m(G) is defined as follow: S₁(G)=S(G).V(S_m(C))=V(C)∪V(G')∪V(G")∪...∪V(G^(m))∪{w}, E(S_m(C))=E(C)∪E(C')∪E(C")∪...∪E(G^(m))∪{v_i^(j)v_i^(j+1)|v_i∈V(G),i=1,2,...,n;j=0, 1,...,m-1;v_i⁽⁰⁾=v_i}∪(v_i^(k)v_j^(k+1)|v_iv_j∈E(C),i,j=1,2,..., n; k=0, 1,..., m-1}∪{v_i^(m)|v_i∈V(G), i=1, 2,..., n}.Theorem 3.2.3 For any simple connected graph G, there is XmaxcT(S(G))=XmaxcT(G)+1.Corollary 3.2.4 If S₀(G)=G∨{w},then XmaxcT(S₀(G))=XmaxcT(G)+1.Theorem 3.2.5 For any simple connected graph G, there is XmaxcT(S_m(G))=xmaxcT(G)+1.Theorem 3.2.6 If C is an outer planar graph and p=2.thenTheorem 3.2.7 If G is an outer planar graph and p=3. then XmaxcT(G)=3.