| For graph G, we use V(G), E(G),Δ(G),δ(G) to denote vertex set, edge set, maximum degree and minimum degree.Suppose that V' is a nonempty subset of V. The subgraph of G whose vertex set is V' and whose edge set is the set of those edges of G that have both ends in V is called the subgraph of G induced by V' and is denoted by G[V']. We say G[V'] is an induced subgraph of G.A subset S is called an independent set of G if no two vertices of S are adjacent in G, and a clique of G if any two vertices of S are adjacent in G.A path is a finite non-null sequence W=v0e1v1e2v2…ekvk whose terms are alternately vertices and edges, for 1≤i≤k, the ends of ei are vi-1 and Vi, and both vertices and edges are distinct. The integer k is the length of W. For a graph G, if vertices u, v are connected, the distance between u,v in G, is the length of a shortest u,v-path in G. The maximum distance between two vertices of G is called the diagram of G.A walk is closed if it has positive length and its origin and terminus are the same. A closed trail whose origin and internal vertices are distinct is a cycle.Two vertices u,v of G are said to be connected if there is a (u,v)-path in G. Thus there is a partition of V into nonempty subsets V1,V2,…,Vt such that two vertices u,v are connected if and only if both u,v belong to the same set Vi. The subgraphs G[V1], G[V2],…,G[Vt] are called the components of G. If G has exactly one component, G is connected.An forest is a graph that contains no cycles. A tree is a connected acyclic forest. If each pair of distinct vertices is joined by an edge in a graph G,then G is called a complete graph.A complete graph on n vertices is denoted by Kn.A bipartite graph is one whose vertex set can be partitioned into two subsets X and Y,,so that each edge has one end in X and one end in Y.A complete bipartite graph is a bipartite graph with bipartition(X,Y)in which each vertex of X is joined to each vertex of Y.If|X|=m,|Y|=n,such a graph is denoted by Km,n.An n-partite graph is one whose vertex set can be partitioned into n subsets X1,X2,…,Xn,so that each edge has one end in Xi and one end in Xj A complete n-partite graph is an n-partite graph with partition X1,X2.…,Xn in which cach vertex of Xi is joined to cach vertex of Xj.If|Xi|=li,such a graph is denoted by Kl1,l2,…,ln.A graph G is defined to be split if there is a partition V=S+K of its vertex set into an independent set S and a clique K.In this paper,we discuss the equitable(t,k,d)-tree coloring of graphs.The equitable(t,k,d)-tree coloring of graph G is defined to be a partition V1,V2,…,Vt of vertex set,such that any component of subgraph G[Vi]is a tree with diagram of at most k and△(G)of at most d(k≥0,d≥0),and‖Vi|-|Vj‖≤1 for any i,j(1≤i<j≤t). The equitable(t,k,d)-tree coloring number is the minimum for which G has an equitable(t,k,d)-tree coloring,and is denoted byχk,d.=The total equitable(t,k,d)-tree coloring number is the minimum t for which G has an equitable(t',k,d)-tree coloring for all t'≥t,and is denoted byχk,d.=First we will discuss the equitable tree coloring of some special graphs, such as complete graphs,split graphs,somplete bipartite graphs K1,n,Kn,n and complete n-partite graph Kl1,l2,…,ln(li=1,1≤i≤k).Next we give three definitions:(1)If x mod n=y,we say Mn(x)=y.(2)Z(x)=max{3,max{k|Mi(x)=0,i≤k}}.(3)W(x)=max{j|[x/i]≥[x/i+1],i≤j}. When the diagrm k=1,for complete bipartite graph,we have: Theorem 0.0.1(1)If M3(m)+M3(n)≥3,χ1(Km,n)=[m/3]+[n/3];(2)If M3(m)+M3(n)≤2 and r=mzn{max{Z(m),Z(n)},W(m),W(n)}, thenχ1,1≡(Km,n)=[m/r+1]+[n/r+1].For complete n-partite graph,we also have similar result.At last,when there is no limitation on k,for complete bipartite graph and complete n-partite graph:we discuss the equitable tree coloring based on the results above. |
