close

Вход

Забыли?

вход по аккаунту

?

328

код для вставкиСкачать
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.
Документ
Категория
Без категории
Просмотров
4
Размер файла
106 Кб
Теги
328
1/--страниц
Пожаловаться на содержимое документа