# Untitled Document

COLORING OF TREES WITH MINIMUM SUM OF COLORS

Tao Jiang and Douglas B. West

j-tao@math.uiuc.edu and west@math.uiuc.edu

University of Illinois, Urbana, IL 61801-2975

Running head: COLORING OF TREES AMS codes: 05C35, 05C55 Keywords: chromatic sum, minimal coloring, strength Written July 1998.    

Abstract. The chromatic sum $`\mathrm{\Sigma }(G)`$ of a graph $`G`$ is the smallest sum of colors among all proper colorings with natural numbers. The strength $`s(G)`$ of $`G`$ is the minimum number of colors needed to achieve the chromatic sum. We construct for each positive integer $`k`$ a tree $`T_k`$ with strength $`k`$ that has maximum degree only $`2k2`$. The result is best possible.

1. INTRODUCTION

A proper coloring of the vertices of a graph $`G`$ is a function $`f:V(G)N`$ such that adjacent vertices receive different labels (colors). The chromatic number $`\chi (G)`$ is the minimum number of colors in a proper coloring of $`G`$. The chromatic sum $`\mathrm{\Sigma }(G)`$ is a variation introduced by Ewa Kubicka in her dissertation. It is the minimum of $`_{vV(G)}f(v)`$ over proper colorings $`f`$ of $`G`$. A minimal coloring of $`G`$ is a proper coloring of $`G`$ such that $`_vf(v)=\mathrm{\Sigma }(G)`$.

One might think that a minimal coloring can be obtained by selecting a proper coloring with the minimum number of colors and then giving the largest color class color $`1`$, the next largest color $`2`$, and so on. However, even among trees, which have chromatic number $`2`$, more colors may be needed to obtain a minimal coloring. The strength $`s(G)`$ of a graph $`G`$ is the minimum number of colors needed to obtain a minimal coloring. Kubicka and Schwenk  constructed for every positive integer $`k2`$ a tree $`T_k`$ with strength $`k`$. Thus $`s(G)`$ may be arbitrarily large even when $`\chi (G)=2`$ (trivially $`s(G)\chi (G)`$).

How large can $`s(G)`$ be in terms of other parameters? When vertices are colored greedily in natural numbers with respect to a vertex ordering $`v_1,\mathrm{},v_n`$, the number of colors used is at most $`1+\mathrm{max}_id^{}(v_i)`$, where $`d^{}(v_i)`$ counts the neighbors of $`v_i`$ in $`\{v_1,\mathrm{},v_{i1}\}`$. Always this yields $`\chi (G)1+\mathrm{\Delta }(G)`$. The best upper bound on $`\chi (G)`$ that can be obtained in this way is the Szekeres-Wilf number $`w(G)=1+\mathrm{max}_{HG}\delta (H)`$ (also confusingly called the “coloring number”). Interestingly, the average of these two well-known upper bounds for the chromatic number is an upper bound for the strength $`s(G)`$.

THEOREM (Hajiabolhassan, Mehrabadi, and Tusserkani ) Every graph $`G`$ has strength at most $`(w(G)+\mathrm{\Delta }(G))/2`$.

We show that this bound is sharp, even for trees. Every nontrivial tree $`T`$ has Szekeres-Wilf number $`2`$, and thus $`s(T)1+\mathrm{\Delta }(T)/2`$. In the Kubicka-Schwenk construction , the tree with strength $`k`$ has maximum degree about $`k^2/2`$. To show that the bound above is sharp, we construct for each $`k1`$ a tree $`T_k`$ with strength $`k`$ and maximum degree $`2k2`$. Given a proper coloring $`f`$ of a tree $`T`$, we use $`\mathrm{\Sigma }f`$ to denote $`_{vV(T)}f(v)`$.

2. THE CONSTRUCTION

Linearly order the pairs of natural numbers so that $`(h,l)<(i,j)`$ if either $`h+l<i+j`$ or $`h+l=i+j`$ and $`l<j`$. With respect to this ordering, we inductively construct for each pair $`(i,j)N\times N`$ a rooted tree $`T_i^j`$ and a coloring $`f_i^j`$ of $`T_i^j`$. In other words, we construct trees in the order $`T_1^1`$, $`T_2^1`$, $`T_1^2`$, $`T_3^1,\mathrm{}`$. Our desired tree with strength $`k`$ will be $`T_k^1`$. Let $`[n]=\{kZ:\mathrm{\hspace{0.17em}1}kn\}`$.

Construction. Let $`T_1^1`$ be a tree of order 1, and let $`f_1^1`$ assign color 1 to this single vertex. Consider $`(i,j)(1,1)`$, and suppose that for each $`(h,l)<(i,j)`$ we have constructed $`T_h^l`$ and $`f_h^l`$. We construct $`T_i^j`$ and $`f_i^j`$ as follows. Let $`u`$ be the root of $`T_i^j`$. For each $`k`$ such that $`1ki+j1`$ and $`ki`$, we take two copies of $`T_k^m`$, where $`m=(i+jk)/2`$, and we let the roots of these $`2(i+j2)`$ trees be children of $`u`$. The resulting tree is $`T_i^j`$ (see Fig. 1). Define the coloring $`f_i^j`$ of $`T_i^j`$ by assigning $`i`$ to the root $`u`$ and using $`f_k^m`$ on each copy of $`T_k^m`$ rooted at a child of $`u`$.   

$``$$``$$``$$``$$``$$``$$``$$`u`$$`\mathrm{}`$$`\mathrm{}`$$`\mathrm{}`$$`\mathrm{}`$$`T_1^{\frac{i+j1}{2}}`$$`T_1^{\frac{i+j1}{2}}`$$`T_k^{\frac{i+jk}{2}}`$$`T_k^{\frac{i+jk}{2}}`$$`T_{i+j1}^1`$$`T_{i+j1}^1`$2 copies2 copies2 copies 

$`1ki+j1`$ and $`ki`$

Figure 1. The construction of $`T_i^j`$

LEMMA  For $`(i,j)N\times N`$, the construction of $`T_i^j`$ is well-defined, and $`f_i^j`$ is a proper coloring of $`T_i^j`$ with color $`i`$ at the root.

Proof: To show that $`T_i^j`$ is well-defined, it suffices to show that when $`(i,j)(1,1)`$, every tree used in the construction of $`T_i^j`$ has been constructed previously. We use trees of the form $`T_k^m`$, where $`k[i+j1]\{i\}`$ and $`m=(i+jk)/2`$. It suffices to show that $`k+mi+j`$ and that $`m<j`$ when $`k+m=i+j`$.

For the first statement, we have $`k+m(i+j+k)/2i+j`$, since $`ki+j1`$. Equality requires $`k=i+j1`$, which occurs only when $`j2`$ and yields $`m=1`$. Thus $`m<j`$ when $`k+m=i+j`$. Since the trees whose indices sum to $`i+j`$ are generated in the order $`T_{i+j1}^1,\mathrm{},T_1^{i+j1}`$, the tree $`T_k^m`$ exists when we need it.

Finally, $`f_i^j`$ uses color $`i`$ at the root of $`T_i^j`$, by construction. Since the subtrees used as descendants of the root have the form $`T_k^m`$ with $`ki`$, by induction the coloring $`f_i^j`$ is proper.   

3. THE PROOF

The two-parameter construction enables us to prove a technically stronger statement. The additional properties of the construction facilitate the inductive proof. Recall that all colorings considered are labelings with positive integers.

THEOREM  The construction of $`T_i^j`$ and $`f_i^j`$ has the following properties:

(1) If $`f^{}`$ is a coloring of $`T_i^j`$ different from $`f_i^j`$, then $`\mathrm{\Sigma }f^{}>\mathrm{\Sigma }f_i^j`$. Furthermore, if $`f^{}`$ assigns a color different from $`i`$ to the root of $`T_i^j`$, then $`\mathrm{\Sigma }f^{}\mathrm{\Sigma }f_i^jj`$;

(2) If $`j=1`$, then $`\mathrm{\Delta }(T_i^j)=2i2`$, achieved by the root of $`T_i^j`$. If $`j2`$, then $`\mathrm{\Delta }(T_i^j)=2(i+j)3`$;

(3) The highest color used in $`f_i^j`$ is $`i+j1`$.

Proof: We use induction through the order in which the trees are constructed. As the basis step, $`T_1^1`$ is just a single vertex, and $`f_1^1`$ gives it color 1; conditions (1)-(3) are all satisfied.

Now consider $`(i,j)(1,1)`$. For simplicity, we write $`T`$ for $`T_i^j`$ and $`f`$ for $`f_i^j`$. To verify (1), let $`f^{}`$ be a coloring of $`T`$ different from $`f`$. We consider two cases.

Case 1.  $`f^{}`$ assigns $`i`$ to the root $`u`$ of $`T`$.

In this case, $`f^{}`$ and $`f`$ differ on $`Tu`$. Recall that $`Tu`$ is the union of $`2(i+j2)`$ previously-constructed trees. The colorings $`f^{}`$ and $`f`$ differ on at least one of these trees. By the induction hypothesis, the total under $`f^{}`$ is at least the total under $`f`$ on each of these subtrees, and it is larger on at least one. Hence $`\mathrm{\Sigma }f^{}>\mathrm{\Sigma }f`$.

Case 2. $`f^{}`$ assigns a color different from $`i`$ to the root $`u`$.

In this case, we need to show that $`\mathrm{\Sigma }f^{}\mathrm{\Sigma }fj`$. Again the induction hypothesis gives $`f^{}`$ as large a total as $`f`$ on each component of $`Tu`$. If $`f^{}(u)i+j`$, then the difference on $`u`$ is large enough to yield $`\mathrm{\Sigma }f^{}\mathrm{\Sigma }fj`$.

Hence we may assume that $`f^{}(u)=k`$, where $`1ki+j1`$ and $`ki`$. Since $`f^{}`$ is a proper coloring, it assigns a label other than $`k`$ to the roots $`v,v^{}`$ of the two copies of $`T_k^m`$ in $`Tu`$, where $`m=(i+jk)/2`$. Since $`f`$ uses $`f_k^m`$ on each copy of $`T_k^m`$, we have $`f(v)=f(v^{})=k`$. Since $`f^{}(v)`$ and $`f^{}(v^{})`$ differ from $`k`$, the induction hypothesis implies that on each copy of $`T_k^m`$ the total of $`f^{}`$ exceeds the total of $`f`$ by at least $`m`$. Since the total is at least as large on all other components, we have

$$\mathrm{\Sigma }f^{}\mathrm{\Sigma }fki+2m=ki+2\frac{i+jk}{2}j.$$

Next we verify (2). In the construction of $`T=T_i^j`$, we place $`2(i+j2)`$ subtrees under the root $`u`$. These have the form $`T_k^m`$ for $`1ki1`$ and $`i+1ki+j1`$, and always $`m=(i+jk)/2`$. Note that $`m=1`$ only when $`k=i+j1`$ or $`k=i+j2`$. The subtrees have maximum degree $`2k2`$ (when $`m=1`$) or $`2(k+m)3`$ (when $`m>1`$). Note that $`2(k+m)3>2k2`$ when $`m1`$. Thus

$$\mathrm{\Delta }(T_k^m)2(k+m)3=2\left(k+\frac{i+jk}{2}\right)3=2\frac{i+j+k}{2}3.$$

Also, we always have $`k+m=(i+j+k)/2`$ for the subtree $`T_k^m`$.

When $`j=1`$ we only have $`ki1`$, and thus $`\mathrm{\Delta }(T_k^m)2(i+1+k)/232i3`$. Hence each vertex in $`Tu`$ has degree at most $`(2i3)+1=2i2`$ in $`T`$. Since $`d_T(u)=2i2`$, we have $`\mathrm{\Delta }(T)=2i2`$, achieved by the root.

When $`j2`$, the values of $`k`$ for the subtrees are $`1ki1`$ and $`i+1ki+j1`$. By the induction hypothesis, the maximum degree of $`T_{i+j1}^1`$ is $`2(i+j1)2=2(i+j)4`$ and is achieved by its root. In $`T`$ this vertex has degree $`2(i+j)3`$, which exceeds $`d_T(u)`$. For $`ki+j2`$, we have $`\mathrm{\Delta }(T_k^m)2(i+j+k)/232(i+j)5`$. Hence $`\mathrm{\Delta }(T)=2(i+j)3`$, achieved by the roots of the trees that are isomorphic to $`T_{i+j1}^1`$.

It remains to verify (3): the maximum color used in $`f_i^j`$ is $`i+j1`$. By the induction hypothesis and the construction, the maximum color used by $`f_k^m`$ on each $`T_k^m`$ within $`f_i^j`$ is $`k+m1=(i+j+k)/21`$. Since the largest $`k`$ is $`i+j1`$ when $`j2`$ and is $`i1`$ when $`j=1`$, this computation yields $`i+j1`$ when $`j2`$ and $`i1`$ when $`j=1`$ as the maximum color on $`Tu`$. Since $`f`$ assigns $`i`$ to the root $`u`$, we obtain $`i+j1`$ as the maximum color on $`T`$ for both $`j2`$ and $`j=1`$.   

We have proved that $`f_i^j`$ is the unique minimal coloring of $`T_i^j`$ and that it uses $`i+j1`$ colors. Hence $`s(T_i^j)=i+j1`$. The maximum degree is $`2i2`$ or $`2(i+j)3`$, depending on whether $`j=1`$ or $`j2`$. In particular, $`T_i^1`$ is a tree with strength $`i`$ and maximum degree $`2i2`$.

COROLLARY 1. There exists for each positive integer $`i`$ a tree $`T_i`$ with $`s(T_i)=i`$ and $`\mathrm{\Delta }(T_i)=2i2`$.   

COROLLARY 2. For every real number $`\alpha (0,1/2)`$, there is a sequence of trees $`T_1^{},T_2^{},\mathrm{}`$ such that $`lim_n\mathrm{}s(T_n^{})/\mathrm{\Delta }(T_n^{})=\alpha `$.

Proof: Let $`t=(\frac{1}{\alpha }2)i+2`$. Consider the construction of $`T_i^1`$. Form $`T_i^{}`$ by adding $`t`$ additional copies of the subtree $`T_{i1}^1`$ under the root $`u`$ of $`T_i^1`$. The strength of $`T_i^{}`$ is $`i`$, but $`\mathrm{\Delta }(T_i^{})=2i2+t`$. As $`i\mathrm{}`$, we have

$$\frac{s(T_i^{})}{\mathrm{\Delta }(T_i^{})}=\frac{i}{2i+t2}=\frac{i}{2i+(\frac{1}{\alpha }2)i}\alpha .$$

References

 P. Erdős, E. Kubicka, and A.J. Schwenk, Graphs that require many colors to achieve their chromatic sum, Congr. Numer. 71(1990), 17–28.

 H. Hajiabolhassan, M.L. Mehrabadi, and R. Tusserkani, Minimal coloring and strength of graphs. Proc. 28th Annual Iranian Math. Conf., Part 1 (Tabriz, 1997), Tabriz Univ. Ser. 377 (Tabriz Univ., Tabriz, 1997), 353–357.

 E. Kubicka, Constraints on the chromatic sequence for trees and graphs, Congr. Numer. 76(1990), 219–230.

 E. Kubicka and A.J. Schwenk, An introduction to chromatic sums, Proc. ACM Computer Science Conference, Louisville(Kentucky) 1989, 39–45.

 C. Thomassen, P. Erdős, Y. Alavi, P.J. Malde, and A.J. Schwenk, Tight bounds on the chromatic sum of a connected graph, J. Graph Theory 13(1989), 353–357.

 Z. Tuza, Contraction and minimal $`k`$-colorability Graphs and Combin. 6(1990), 51–59.