Some Results on the Achromatic Number Niall Cairnie and Keith Edwards DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE UNIVERSITY OF DUNDEE DUNDEE, DD1 4HN, U.K. E-mail: kedwards@mcs.dundee.ac.uk Received June 26, 1996; revised June 4, 1997 Abstract: Let G be a simple graph. The achromatic number ψ(G) is the largest number of colors possible in a proper vertex coloring of G in which each pair of colors is adjacent somewhere in G. For any positive integer m, let q(m) be the largest integer k such that (k2 ) ≤ m. We show that the problem of determining the achromatic number of a tree is NP-hard. We further prove that almost all trees T satisfy ψ(T ) = q(m), where m is the number of edges in T . Lastly, for fixed d and > 0, we show that there is an integer N0 = N0 (d, ) such that if G is a graph with maximum degree at most d, and c 1997 John Wiley & Sons, Inc. J Graph Theory m ≥ N0 edges, then (1 − )q(m) ≤ ψ(G) ≤ q(m). 26: 129–136, 1997 Keywords: achromatic number, harmonious chromatic number, NP-completeness 1. INTRODUCTION A pair-complete coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at least one edge. The achromatic number ψ(G) is the largest integer i for which G admits a pair-complete coloring with i colors (note that the chromatic number χ(G) is the least integer j for which G admits a pair-complete coloring with j colors). The achromatic number was introduced by Harary, Hedetniemi and Prins [12] and by Harary and Hedetniemi [11]. Surveys on the achromatic number have been written by Hughes and MacGillivray [15] and Edwards [5], with the latter also covering the harmonious chromatic number, which we define next. c 1997 John Wiley & Sons, Inc. CCC 0364-9024/97/030129-08 130 JOURNAL OF GRAPH THEORY A harmonious coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number h(G) is the least integer k for which G admits a harmonious coloring with k colors. Harmonious coloring developed from the closely related concept of line-distinguishing coloring which was introduced independently by Frank, Harary and Plantholt [8] and by Hopcroft and Krishnamoorthy [14]. A line-distinguishing coloring of a simple graph G is a coloring of vertices of G such that each pair of colors (including color pairs of the form {i, i}) appears together on at most one edge. Clearly, such a coloring need not be proper. At this point it is helpful to introduce the following definition. Definition. Let m be a positive integer. Then we define Q(m) to be the least positive integer k t√ such that (t2 ) ≤ m. It is easily calculated such that (k2 ) ≥ m, and √q(m) to be the largest integer 1 1 that Q(m) = d 2 (1 + 8m + 1)e and q(m) = b 2 (1 + 8m + 1)c. Remark. For any graph G with m edges, it is immediate that h(G) ≥ Q(m), since in any harmonious coloring there must be at least as many pairs of colors as there are edges. Similarly, for any graph G with m edges, ψ(G) ≤ q(m), since G does not have enough edges to support a pair-complete coloring with more than q(m) colors. In this paper, we use some recent results on harmonious chromatic number to prove fresh results on achromatic number. This is made possible by the following relationship, which has only recently been noted [5]: if G is a graph with exactly (k2 ) edges, then a proper vertex coloring of G with k colors is pair-complete if and only if it is harmonious (the proof of this is trivial; we omit the details). In view of this, the next lemma, stated without proof, follows easily. Lemma 1.1. Let G be a graph with (k2 ) edges. Then ψ(G) = k if and only if h(G) = k. As will be shown in this paper, we can make use of this ‘‘duality’’ even when considering graphs which do not have exactly (k2 ) edges. We will refer to a graph as exact if it has exactly (k2 ) edges, for some positive integer k. Yannakakis and Gavril [17] proved that the problem of determining the achromatic number of a graph is NP-hard. In Section 2, we show that the problem remains NP-hard even when restricted to trees, as conjectured by Hedetniemi, Hedetniemi, and Beyer [13]. This result is interesting as it is rather rare for a natural graph-theoretic problem to be NP-hard for trees. In Section 3, it is shown that almost all trees T satisfy ψ(T ) = q(m), where m is the number of edges in T . Lastly, in Section 4, we turn our attention to graphs of bounded degree. Let d be a fixed positive integer and let > 0. We prove that there is an integer N0 = N0 (d, ) such that if G is any graph with maximum degree at most d and m ≥ N0 edges, then (1 − )q(m) ≤ ψ(G) ≤ q(m). It can also be shown that for a fixed positive integer d, there is a natural number N = N (d) such that if T is any tree with maximum degree at most d and m ≥ N edges, then ψ(T ) is q(m) or q(m) − 1. A polynomial time algorithm for determining the achromatic number of a tree with maximum degree at most d can also be derived. However, these two results on bounded degree trees will be dealt with in a subsequent paper. 2. THE COMPLEXITY OF DETERMINING ψ(T ) FOR A TREE T Yannakakis and Gavril [17] proved that the problem of determining the achromatic number of a graph is NP-hard, and Farber et al. [7] showed that the problem remains NP-hard when restricted SOME RESULTS ON THE ACHROMATIC NUMBER 131 to bipartite graphs. More recently, Bodlaender [1] proved that the problem remains NP-hard when restricted to connected graphs that are simultaneously a cograph and an interval graph. In this section, we show that the problem of determining the achromatic number of a tree is NP-hard, as conjectured by Hedetniemi, Hedetniemi and Beyer [13]. Firstly, we quote a theorem of Geller and Kronk [10]: Theorem 2.1 [10]. For any graph G and vertex u in G, we have ψ(G) ≥ ψ(G − u) ≥ ψ(G) − 1, where G − u is the subgraph of G which is formed by removing vertex u (and all edges that were incident to u). We now come to the main result of this section. Theorem 2.2. The following problem is NP-complete: Instance Tree T , integer k. Question Is ψ(T ) ≥ k? Proof. The problem is obviously in NP. We reduce from the NP-complete problem TREE HARMONIOUS CHROMATIC NUMBER [6]: Instance Tree T , integer C. Question Is h(T ) ≤ C? Note that we may restrict ourselves to instances of this problem where T has at most (C2 ) edges, since trivially h(T ) 6≤ C for instances where this is not the case. So let T and C be an instance of TREE HARMONIOUS CHROMATIC NUMBER where T has m ≤ (C2 ) edges. We now set k = C + 1 and construct a tree T 0 as follows: Take a new vertex u and join it to a vertex in T . Take C further new vertices v1 , v2 , . . . , vC and join them all to u. Let r = (C2 ) − m. Take 2r more new vertices w1 , w2 , . . . , wr and x1 , x2 , . . . , xr and insert the edges {u, wi } and {wi , xi } for each 1 ≤ i ≤ r. An example is shown in Figure 1 below. In this example, T has m = 4 edges, and C = 4, so that r = 2. It is clear that T 0 and k are easily constructed in polynomial time. We claim that ψ(T 0 ) ≥ k if and only if h(T ) ≤ C. Suppose that ψ(T 0 ) ≥ k. Let T 0 − u be the subforest of T 0 that is formed by deleting vertex u (and all edges that were incident to u). Note that T 0 − u is the disjoint union of T , the isolated vertices v1 , . . . , vC and the r isolated edges of the form {wi , xi }. Thus, T 0 − u has (C2 ) = (k−1 2 ) edges, and so ψ(T 0 − u) ≤ k − 1. But then by Theorem 2.1, ψ(T 0 ) ≤ k, and so ψ(T 0 ) = k. Reapplying Theorem 2.1, we obtain ψ(T 0 − u) = k − 1 = C. Thus, by Lemma 1.1, h(T 0 − u) = C, FIGURE 1. 132 JOURNAL OF GRAPH THEORY and there is a harmonious coloring of T 0 − u with C colors which induces a harmonious coloring of T with at most C colors. Hence, h(T ) ≤ C. Conversely, suppose that h(T ) ≤ C. Then certainly there is a harmonious coloring γ of T with C colors in which r of the possible (C2 ) color pairs are unused. Now, for i = 1, . . . , r, we choose γ(wi ) and γ(xi ) so that each of the r unused color pairs appears on an edge of form {wi , xi }. We then let γ(u) = C + 1, and let γ(vj ) = j for each 1 ≤ j ≤ C. It is clear that this results in a pair-complete coloring of T 0 with C + 1 = k colors, and so ψ(T 0 ) ≥ k. The result follows. Remarks. (1) Theorem 2.1 suggests the following upper bound for the achromatic number of a graph: If G is a graph with m edges and maximum vertex degree ∆, then ψ(G) ≤ min{q(m), q(m − ∆) + 1}. The proof of this is straightforward and is left to the reader. (2) In view of Lemma 1.1, we note that the proof given by Bodlaender [1] also establishes that it is an NP-hard problem to determine the harmonious chromatic number of an unconnected graph which is simultaneously a cograph and an interval graph. (3) A cograph is a graph which does not contain a path with four vertices as an induced subgraph. We note that the problem of determining the harmonious chromatic number of a connected cograph is trivial, since in such a graph each vertex must receive a distinct color as it is at most distance 2 from all other vertices. This is interesting since the problem of determining the achromatic number of a connected cograph is NP-complete [1]. 3. THE ACHROMATIC NUMBER OF ALMOST ALL TREES In this section we show that almost all trees T satisfy ψ(T ) = q(m), in the normal sense that the proportion of trees on n vertices with this property tends to 1 as n tends to infinity. We require some properties of random (unlabeled, unrooted) trees. Lemma 3.1. Almost all trees on n vertices have at least n/3 leaves. Proof. This follows easily, by Chebyshev’s inequality, from the work of Robinson and Schwenk [16], who showed that the number of leaves in a random (unlabeled, unrooted) tree has mean about (0.438)n and variance about (0.192)n. The following two lemmas were proved in [2]. Lemma 3.2 [2]. Almost all trees on n vertices have maximum degree at most K log n, for some constant K > 0. Lemma 3.3 [2]. Let k be a positive integer. Then there is a constant bk such that the expected total degree of the vertices of degree at least k in a random tree on n vertices is less than 2bk n provided n is large enough. Furthermore, provided k is large enough, bk ≤ 7kρk /(1 − ρ)2 , where ρ ≈ 0.338. We will also make use of a result on harmonious coloring [2]: Lemma 3.4 [2]. Let d be a positive integer. Then provided d is large enough, there exists an integer N = N (d) such that the following holds: let T be any tree with n ≥ N vertices satisfying (i) the maximum degree is at most K log n, where K > 0 is a constant, (ii) the total degree of the vertices of degree greater than d is at most n/2d , (iii) T has at least n/4 leaves. Then h(T ) = Q(m). We may now state and prove the main result of this section. SOME RESULTS ON THE ACHROMATIC NUMBER 133 Theorem 3.5. For almost all trees T , the achromatic number ψ(T ) of T is q(m), where m is the number of edges of T . Proof. Let > 0. We will show that provided n is sufficiently large, the proportion of trees T on n vertices for which ψ(T ) = q(m) is at least 1 − . We choose d such that d is large enough to allow the existence of an integer N = N (d) as described in Lemma 3.4, and such that 14d2d+1 ρd /(1 − ρ)2 ≤ /2, where ρ ≈ 0.338. Now, by Lemma 3.3, the expected total degree of the vertices of degree greater than d in a tree on n vertices is at most (14dρd /(1 − ρ)2 )n, and so, by the Markov inequality, the proportion of trees on n vertices for which this total degree is more than n/2d+1 is at most /2. Also, by Lemma 3.1 and Lemma 3.2, provided that n is large enough, the proportion of trees on n vertices with fewer than n/3 leaves or maximum degree greater than K log n is at most /2. Hence, all of the remaining trees, that is a proportion at least 1 − of the trees T on n vertices satisfy: (a) the maximum degree of T is at most K log n, where K > 0 is a constant, (b) the total degree of the vertices of degree greater than d is at most n/2d+1 , and (c) T has at least n/3 leaves. Thus, to prove the overall result it suffices to show that if n is sufficiently large, ψ(T ) = q(m) for any tree T on n vertices satisfying conditions (a), (b) and (c), where m = n − 1. So let T be a tree on n vertices satisfying conditions (a), (b) and (c), let m = n − 1 and q(m) q(m) q(m)+1 q(m) let r = m − ( 2 ). Then r is O(n1/2 ) at most, since r = m − ( 2 ) < ( 2 ) − ( 2 ) 0 = q(m). Therefore, if n is large enough, we can delete r leaves from T to form a tree T with n0 ≥ q(m) N (d) vertices and at least n0 /4 leaves. Then T 0 has m0 = ( 2 ) edges. Let ∆ be the maximum vertex degree in T 0 . It is clear that ∆ ≤ K log n. Let K 0 = 2K. Then, if n is large enough, ∆ ≤ K 0 log n0 , and so, T 0 satisfies condition (i) of Lemma 3.4. Also, if n is large enough, the total degree of the vertices in T 0 which have degree greater than d is at most n/2d+1 ≤ n0 /2d . Hence, if n is large enough, T 0 satisfies all of the conditions of Lemma 3.4, and so h(T 0 ) = Q(m0 ) = q(m). Thus, by Lemma 1.1, ψ(T 0 ) = q(m), and there is a pair-complete coloring γ of T 0 with q(m) colors. Since T 0 was obtained from T by deleting leaves, it is clear that γ can be extended to a pair-complete coloring of T with q(m) colors. Hence, ψ(T ) = q(m), and the overall result follows. 4. GRAPHS OF BOUNDED DEGREE We have seen that for a graph G with m edges, ψ(G) ≤ q(m). In this section we show that this bound is asymptotically tight for graphs of bounded degree. We will make use of a result on harmonious chromatic number [4]: Theorem 4.1 [4]. Let d be a fixed integer, and let > 0. Then there is an integer M0 = M0 (d, ) such that if G is a graph with maximum degree at most d, and G has m edges, where m ≥ M0 , then h(G) ≤ (1 + )(2m)1/2 . Note that both Q(m) and q(m) are asymptotically identical to (2m)1/2 . We may now state and prove a result for achromatic number that is analogous to Theorem 4.1. Theorem 4.2. Let d be a fixed integer, and let > 0. Then there is an integer N0 = N0 (d, ) such that if G is a graph with maximum degree at most d, and G has m edges, where m ≥ N0 , then ψ(G) ≥ (1 − )(2m)1/2 . 134 JOURNAL OF GRAPH THEORY Proof. We repeat the following until we have removed at least bmc − 2d2 + 1 edges from G: (i) remove an edge {u, v} and place it in a set X, (ii) for each neighbor w of u or v, delete all edges incident to w, and (iii) remove any isolated vertices which result. Each time we perform steps (i), (ii) and (iii) we remove fewer than 2d2 edges. Once the above has been completed, we are left with a graph G∗ , say. Let R be the number of edges that were removed from G to form G∗ . Clearly, bmc − 2d2 + 1 ≤ R < bmc. In general, |X| will be much smaller than R, but certainly |X| ≤ R < bmc. We now form a graph G0 with m0 = m − bmc edges by arbitrarily removing bmc − R edges from G∗ (we do not insert any of these edges into the set X). Let 0 = /(6d2 ). Then the number of edges in X is bmc − 2d2 + 1 2d2 (m − 1) − 2d2 + 1 ≥ 2d2 m ≥ −1 2d2 ≥ 30 m0 − 1. |X| ≥ Now, if m ≥ N1 , say, we have m0 ≥ M0 (d, 0 ), and so, by Theorem 4.1, there is a harmonious coloring γ 0 of G0 with k = b(1 + 0 )(2m0 )1/2 c colors. Then k satisfies k ≥ Q(m0 ) ≥ (2m0 )1/2 ≥ (2(m − bmc))1/2 1/2 bmc = 1− (2m)1/2 m bmc (2m)1/2 ≥ 1− m ≥ (1 − )(2m)1/2 . Q(m)−1 As an immediate consequence of the definition of Q(m), we have that ( 2 ) < m, from which it easily follows that (Q(m))2 < 2m + 3Q(m) − 2. Let S be the set of all color pairs {a, b} that are not used in γ 0 , where 1 ≤ a < b ≤ k. Then the number of color pairs in S is k |S| = − m0 2 (1 + 0 )Q(m0 ) ≤ − m0 2 ≤ 12 (1 + 0 )2 (Q(m0 ))2 − m0 ≤ 12 (1 + 20 + (0 )2 )(Q(m0 ))2 − m0 ≤ 12 (1 + 20 + (0 )2 )(2m0 + 3Q(m0 ) − 2) − m0 ≤ 20 m0 − 1 + ( 32 + 30 )Q(m0 ) − 20 + 12 (0 )2 (2m0 + 3Q(m0 ) − 2). SOME RESULTS ON THE ACHROMATIC NUMBER 135 √ Now, Q(m0 ) is O( m0 ). Hence, if m ≥ N2 , say, we will have m0 large enough to ensure that |S| ≤ 30 m0 − 1 ≤ |X|. This being so, we have (k2 ) = |S| + m0 ≤ |X| + m0 = |X| + m − bmc < m, since |X| < bmc. Hence, k ≤ q(m). Let γ be the partial coloring of G with k colors that is induced by the coloring γ 0 of G0 . We will show that γ can be extended to a pair-complete coloring of G. For each edge {u, v} ∈ X, it is clear that vertices u and v, and any neighbors of u or v, are uncolored under γ. Also, no two edges in X are incident in G. Furthermore, in G, an endpoint u of an edge {u, v} ∈ X is not adjacent to an endpoint of any other edge in X. Hence, we may color the endpoints of an edge in X with any pair of distinct colors we wish. If m ≥ N3 , say, we have k ≥ d + 1. This being so, we color the endpoints of |S| edges in X in a way that uses all of the color pairs in the set S. We have now used all of the (k2 ) possible color pairs. We then color each uncolored vertex in G with any existing color that has not yet been assigned to any of its at most d neighbors. It is clear that this results in a pair-complete coloring of G with k ≥ (1 − )(2m)1/2 colors. Since q(m) ∼ (2m)1/2 , we have ψ(G) = (1 − o(1))q(m). Choosing N0 = max{N1 , N2 , N3 } completes the proof. 5. CONCLUDING REMARKS We have seen that determining ψ(T ) for a tree T is NP-hard. In view of this, and the result due to Bodlaender [1], we may well assume that the problem of determining the achromatic number will remain NP-hard unless restricted to a class of graphs that is either (i) reasonably trivial, or (ii) of bounded degree. Two interesting related open problems are the complexities of determining ψ(G) and h(G), respectively, for a graph G of maximum degree d, where d is a fixed integer. We have also seen that almost all trees satisfy ψ(T ) = q(m). We might wish to consider other classes of graphs to ascertain whether or not almost all members of the class have achromatic number equal to q(m). References [1] H. L. Bodlaender, Achromatic number is NP-complete for cographs and interval graphs, Inform. Process. Lett. 31 (1989), 135–138. [2] K. J. Edwards, The harmonious chromatic number of almost all trees, Combinatorics, Probability and Computing 4 (1995), 31–46. [3] K. J. Edwards, The harmonious chromatic number of bounded degree trees, Combinatorics, Probability and Computing 5 (1996), 15–28. [4] K. J. Edwards, The harmonious chromatic number of bounded degree graphs, J. London Math. Soc. 55 (1997), 435–447. [5] K. J. Edwards, The harmonious chromatic number and the achromatic number, In: Surveys in Combinatorics 1997 (Invited papers for 16th British Combinatorial Conference) (Ed., R. A. Bailey), Cambridge University Press, Cambridge (1997), 13–47. [6] K. J. Edwards and C. J. H. McDiarmid, The complexity of harmonious colouring for trees, Discrete Appl. Math. 57 (1995), 133–144. [7] M. Farber, G. Hahn, P. Hell, and D. Miller, Concerning the achromatic number of graphs, J. Combin. Theory Ser. B 40 (1986), 21–39. [8] O. Frank, F. Harary, and M. Plantholt, The line-distinguishing chromatic number of a graph, Ars Combin. 14 (1982), 241–252. 136 JOURNAL OF GRAPH THEORY [9] M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NPcompleteness, Freeman, New York (1980). [10] D. Geller and H. Kronk, Further results on the achromatic number, Fund. Math. 85 (1974), 285–290. [11] F. Harary and S. T. Hedetniemi, The achromatic number of a graph, J. Combin. Theory 8 (1970), 154–161. [12] F. Harary, S. T. Hedetniemi, and G. Prins, An interpolation theorem for graphical homomorphisms, Portugal. Math. 26 (1967), 453–462. [13] S. M. Hedetniemi, S. T. Hedetniemi, and T. Beyer, A linear algorithm for the Grundy (coloring) number of a tree, In: Proc. 13th S-E Conference on Combinatorics, Graph Theory and Computing, Boca Raton 1982, Congr. Num. 36 (1982), 351–363. [14] J. E. Hopcroft and M. S. Krishnamoorthy, On the harmonious coloring of graphs, SIAM J. Alg. Discrete Meth. 4 (1983), 306–311. [15] F. Hughes and G. MacGillivray, The achromatic number of graphs: a survey and some new results, Bull. Inst. Combin. Appl. 19 (1997), 27–56. [16] R. W. Robinson and A. J. Schwenk, The distribution of degrees in a large random tree, Discrete Maths. 12 (1975), 359–372. [17] M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38 (1980), 364–372.

1/--страниц