The Edge-restricted Vertex Coloring Of Graphs

All graphs considered in this paper are finite simple graphs. The present pa-per attempts to extend the vertex-chromatic and achromatic to the edge-restricted vertex coloring of graphs. Let Pn be the path of length n - l.Lct Kn be a complete graph with n verttices. Let Kn,n be a complete bipartite. Let G V H denote the join of graphs G and H.Let Km(n) be a complete muti-partite graph with n vertices in each part.Achromatic numberα(G) of a graph G is a maximum number of colours in a proper vertex colouring of G such that vertices of any two distinct colour classes arc joined by at least one ege. By a pseudocoloring of the vertices of a graph G, we mean a coloring in which adjacent vertices can receive the same color. A pseudocomplete coloring of a graph G is a pseudocoloring of the vertices of G,such that for any pair of distinct colors, there is at least one edge which end vertices are colored with this pair of colors. The pseudoachromatic numberψ(G) of a graph G is the greatest number of colors in a pseudocomplete coloring of a graph G.к-pseudocomplete coloring of a graph G is a pseudocoloring of the vertices of G, such that for any pair of distinct colors, there are at least k edges which end vertices are colored with this pair of colors.The edge-restricted vertex coloring of graphs numberψk(G) of a graph is the greatest number of colors in a k- pseudocomplete coloring of G. When k =1,the edge-restricted vertex coloring of graphs is the pseudoachromatic. There are some results that we have proved:Therom 1 For any positive number t, t = 2k+1, there is a path Pn which satisfiesψ2(Pn)= 2k+1, and min|V(Pn)|= 2k(2k+1)+1.Corollary 1 There is a path P which satisfiesψm(P)= 2k+1 and|V(P)|= mk(2k+1)+1. Theorem 2 For any positive number t,t=2k,there is a path Pn which satisfiesψ2(Pn)=2k and min |V(Pn)|=2k(2k+1)+1Corollary 2 There is a path P which satisfiesψm(P)=2k,and min |V(P)|= tA(?)k+1,m=2t,or min |V(P)|=(tA(?)k+1)+(2k2-1),m=2t+1.Theorem 3ψ2(kn)=[(?)],when n=2k+l,ψ2(Kn)=k+1；when n=2k,ψ2(kn)=k.Theorem 4ψm(Kn)=[(?)] orψm(Kn)=[(?)](m≥3).Theorem 5ψm(kn,n)=[(?)] orψm(Kn,n)=[?](m≥2).Theorem 6 For a simple graph G,△is maximum degree and |V(G)|=p,then p≥n[(?)].n=ψm(G).Theorem 7 G=K3(n)thenψ2(G)=(?).Theorem 8 Let G=Km(n)thenψ2(G)=(?)Theorem 9 Let 3≤t1≤t2≤...≤tk be positive integers and let∑(?)=P·If k≤(?).thenψ(Ct1∪Ct2...∪Ctk) =ψ(Cp).Theorem 10 For most positive integer k,thenψ(kC4)=ψ(C4k).