On Colorings of Squares of Outerplanar Graphs Geir Agnarsson Magnus M. Halld´rsson ´ o Abstract We investigate the clique number, the chromatic number and the inductiveness (or the degeneracy) of the square G2 of an outerplanar graph G, and bound as a function of the maximum degree of G. Our main result is a tight bound of for the inductiveness of the square of any outerplanar graph G, when 7. This implies that a greedy algorithm yields an optimal coloring of such square graphs, and leads to an exact linear time algorithm that holds for any . We then derive optimal upper bounds on the three parameters for outerplanar graphs of smaller degree < 7, and in the case of chordal outerplanar graphs, classify exactly which graphs have parameters exceeding the absolute minimum. A co-product of the study is a characterization of all strongly simplicial elimination orderings of an arbitrary power of a tree. 1 Intro duction The square of a graph G is the graph G2 on the same vertex set with edges between pair of vertices of distance one or two in G. Coloring squares of graphs has been studied in relation to frequency allocation. This models the case when nodes represent both senders and receivers, and two senders with a common neighbor will interfere if using the same frequency. The problem has particularly seen much attention on planar graphs. A conjecture of Wegner [1] dating from 1977 (see [2]), states that the square of every planar graph G has a chromatic number which does not exceed 3/2 + 1, where 8 is the maximum degree of G. The conjecture matches the the maximum clique number of these graphs. Currently the best upper bound known is 1.66 + 78 by Molloy and Salavatipour [16]; see [16, 3] for more history of on these problems. An earlier paper of the current authors [3] gave a bound of 1.8 for the chromatic number of squares of planar graph with large maximum degree 749. This is based on bounding the inductiveness of the of Mathematical Sciences, George Mason University, MS 3F2, 4400 University Drive, Fairfax, VA 22030, geir@math.gmu.edu. Department of Computer Science, University of Iceland, Reykjav´k, Iceland. mmh@hi.is i Department graph, which is the maximum over all subgraphs H of the minimum degree of H . It was also shown that this was the best possible bound on the inductiveness. Borodin et al [17] showed that the bound holds for all 48. Inductiveness has the additional advantage of also bounding the list-chromatic number. Inductiveness leads to a natural greedy algorithm (henceforth called Greedy): Select vertex u of minimum degree, recursively color G \ u, and finally color u with the smallest available color. Alternatively, t-inductiveness leads to an inductive ordering u1 , u2 , . . . , un of the vertices such that any vertex ui has at most t neighbors among {ui+1 , . . . , un }. Then, if we color the vertices first-fit in the reverse order un , un-1 , . . . , u1 (i.e. assigning each vertex the smallest color not used among its previously colored neighbors), the number of colors used is at most t + 1. Implemented efficiently, the algorithm runs in time linear in the size of the graph. The algorithm has also the special advantage that it requires only the square graph G2 , and does not require information about the underlying graph G. The purpose of the article is to further contribute to the study of various vertex colorings of squares of planar graphs, by examining an important subclass of them, the class of outerplanar graphs. Observe that the neighborhood of vertex with neighbors induces a clique in the square graph. Thus, the chromatic number, and in fact the clique number, of any graph of maximum degree is necessarily a function of and always at least + 1. Our results. We derive tight bounds on chromatic number, as well as the inductiveness and clique number, of the square of an outerplanar graph G as a function of the maximum degree of G. The main result, given in Section 3, is that when 7, the inductiveness of G2 is exactly . It follows that the clique and chromatic numbers are exactly + 1 and that Greedy yields an optimal coloring. We can then treat the lowdegree cases separately to derive a linear-time algorithm independent of . We examine in detail in Section 4 the low-degree cases, < 7, and derive best possible upper bounds on the maximum clique and chromatic numbers, as well as inductiveness, of squares of outerplanar graphs. We treat the special case of chordal outerplanar graphs Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 244 separately. The results are shown in Table 1. Only in the case of general outerplanar graphs of maximum degree = 5, is it open whether the chromatic number can exceed + 1 (but is known to be at most + 2). We further classify all chordal outerplanar graphs G for which the inductiveness of G2 exceeds or the clique or chromatic number of G2 exceed + 1. 2 3 4 5 6 7+ (G2 ) +1 +1 +2 +1 +1 +1 Chordal ind +1 +1 +1 +1 +1 +2 +1 +2 +1 Non-chordal ind +3 +2 +3 +2 +1 +2 +2 +2 +2 + 1 + 1 + 2? +1 +1 +2 +1 +1 Table 1: Optimal upper bounds for the clique number, inductiveness, and chromatic number of the square of a chordal / non-chordal outerplanar graph G. Since the inductiveness a biconnected outerplanar graph G is closely related to the weak dual T (G), we study in some depth strong simplicial elimination orderings of an arbitrary power of a tree, and characterize all such orderings, but this analysis is omitted for lack of space. In the next section, we introduce our notation and definitions, and show how the problems reduce to the case of biconnected outerplanar graphs with no non-trivial clique separator. Related results. It is straightforward to show that the inductiveness of a square graph of an outerplanar graph of degree is at most 2 (see [3]), and this is attained by an inductive ordering of G. We are not aware of other work analyzing colorings of squares of outerplanar graphs. Zhou, Kanari and Nishizeki [15] gave a polynomial time algorithm to find an optimal coloring of any power of a partial k -tree G, given G. Since outerplanar graphs are partial 2-trees, this solves the coloring problem we consider. For squares of outerplanar graphs, their 37 algorithm has complexity O(n( + 1)2 + n3 ), which is infeasible for moderate to large values of and large for small values of . When is constant, one can use the observation of Krumke, Marathe and Ravi [14] H G that squares of outerplanar graphs have treewidth at O (k ) most k 3 - 1. Thus, one can use efficient (2 n where H runs through all the induced subgraphs of G. time) algorithms for coloring partial k -trees, obtaining If k ind(G) then we say that G is k -inductive. a linear-time algorithm when is constant. Note that for any u V (G), the vertex set NG [u] 2 Definitions and preliminary results In this section we give some basic definitions and prove results that will be used later for our main result. Graph notation. The set {1, 2, 3, . . .} of natural numbers will be denoted by N. By coloring we will always mean vertex coloring. We denote by (G) the chromatic number of G and by (G) the clique number of G. The degree of a vertex u in graph G is denoted by dG (u). Let (G) ((G)) denote the minimum (maximum) degree of a vertex in G. (When there is no danger of ambiguity, we simply write instead of (G).) We denote by NG (u) the open neighborhood of u in G, that is the set of all neighbors of u in G, and by NG [u] the closed neighborhood of u in G, that additionally includes u. The distance dG (u, v ) between vertices u and v is the number of edges in the shortest path between them. When the graph in question is clear from context, we omit the subscript in the notation. For k N, the power graph Gk is a graph with the same vertex set as G, but where every pair of vertices of distance k or less in G are connected by an edge. In particular G2 is the graph in which every two vertices with a common neighbor in G are connected with an edge. The closed neighborhood of a vertex u in Gk will k be denoted by NG [u], and the degree of vertex u will be denoted by dk (u). Tree terminology. The leaves of a tree T will be denoted by L(T ). The diameter of T is the number of edges in the longest simple path in T and will be denoted by diam(T ). For a tree T with diam(T ) 1 we can form the pruned tree pr(T ) = T \ L(T ). A center of T is a vertex of distance at most diam(T )/2 f rom all other vertices of T . A center of T is either unique, or one of two unique adjacent vertices. Clearly, the power graph T k of a tree T , is only interesting when k {1, . . . , diam(T )}. When T is rooted at r V (T ), the k -th ancestor, if it exists, of a vertex u is the vertex on the path from u to r of distance k from u, and is denoted by ak (u). An ancestor of u is a vertex of the r form ak (u) for some k 0. Note that u is viewed as r an ancestor of itself. When u is some vertex of T , the distance dT (u, r) to the root r will be referred to as the level of u and denoted by l(u) when there is no danger of ambiguity. A tree is said to be ful l if it contains no degree-two vertices. Inductiveness. The inductiveness or the degeneracy of a graph G, denoted by ind(G) N is defined by ind(G) = max { (H )} , 245 will induce a clique in G2 , and hence (G2 ), (G2 ) 2. T (G) has maximum degree at most three, if G is 2 2 + 1. Since ind(G ) + 1 (G ), the upper bound chordal. of ind(G) is necessarily an increasing function f () of Note that for a biconnected chordal graph G, there is a N. one-to-one correspondence u u between the degreeCutp oints and biconnectivity. We first show two vertices u of G, and the leaves u of T (G). that we can assume without loss of generality that G We say that leaves of a tree are siblings if they is biconnected. Let G be a graph and B the set of are connected to a common vertex, which we call their its biconnected blocks. In the same way that (G) = parent. By Lemma 2.2, T (G) for a chordal graph G is maxB B { (B )} and (G) = maxB B {(B )}, we have a tree of maximum degree three, and hence each of its the following. leaves has at most one sibling. Strong simplicial vertex orderings of trees. Lemma 2.1. For a graph G with a maximum degree We give a characterization of strong simplicial eliminaand set B of biconnected blocks we have tion orderings of the vertices of the k -th power of a tree. Recall the following definition [11, 12]. 2 2 (G ) = max{max{ (B )}, + 1}, B B Definition 2.3. A vertex u in a graph G is simplicial if NG [u] induces a clique in G. If u is simplicial and {NG [v ] : v NG [u]} is linearly ordered by set inclusion Further, optimal (B 2 )-colorings of the squares of al l then u is strongly simplicial. the blocks B 2 can be modified to a (G2 )-coloring of G2 Any power T k of a tree T is strongly chordal [6, 12], and in a greedy fashion. hence has a strong simplicial elimination ordering of the Proof. We use induction on b 2, the number of blocks vertices V (T ) = {u1 , . . . , un } such that each vertex ui in G. is strongly simplicial in the subgraph of T k induced by Let B be a block corresponding to a leaf in the the previous vertices u1 , . . . , ui-1 . Clearly, a vertex of block-cutpoint tree BC(G). In this case B has a a tree is strongly simplicial if it is a leaf, which gives single cut-vertex, which induces a ( + 1)-clique in us a complete description of when exactly an ordering G2 . Further, any legitimate coloring of the other b - 1 is a strong simplicial ordering of the tree. We give blocks for G2 can by a suitable permutation of colors, a similarly complete description for higher powers of Ne extended to that of B and hence all of G. b graphs. (G ) = 2 max{max{(B 2 )}, + 1}. B B ote that Lemma 2.1 provides a way to extend coloring of each block of G to the whole of G, so by Lemma 2.1 we can assume our graphs are biconnected, both when considering clique and chromatic numbers of G2 . For the inductiveness of G2 , such an extension property as Lemma 2.1, to express ind(G2 ) directly in terms of and the inductiveness of the blocks of G, is not as straightforward. There we need to consider with great care how the simplicial vertices of G2 are chosen. Note that the biconnected components for outerplanar graphs on three or more vertices are precisely those subgraphs induced by simple cycles [8, p. 240]. Duals of outerplanar graphs. To analyze the inductiveness of an outerplanar graph G, it is useful to consider the weak dual T (G). For a tree T we can recursively define T (i) by T (0) T ( i) = T, = pr(T (i-1) ), as long as T (i-1) has leaves, that is, is neither empty nor one vertex. With this notation we obtain the following. Proposition 2.1. Let T be a tree with diam(T ) = d 2. For u V (T ) and k {1, . . . , (d - 1)/2 } the fol lowing are equivalent: 1. For a center c V (T ), the vertex ak-1 (u) is a leaf c of T (k-1) . 2. u is strongly simplicial in T k . Lemma 2.2. Let G be an outerplanar graph with an This proposition follows from an alternative charembedding in the plane. Let G be its geometrical dual, and let u V (G ) be the vertex corresponding to the acterization, based on the following definition. infinite face of G. Then the weak dual graph T (G) = Definition 2.4. Let T be a tree and k 1. We say G \ {u } is a forest which satisfies the fol lowing: that a vertex u V (T ) is k -simple if for some r Ru , 1. T (G) is tree iff G is biconnected. the fol lowing statement holds: 246 Pu;k (r) : If the k -th ancestor ak (u) does not r exist, then T k is a complete graph. If ak (u) r exists then dT (v , ak-1 (u)) k - 1 for al l r v Dr [ak-1 (u)]. r It can be shown that the truth value of Pu;k (r) is independent of r Ru . We omit the somewhat lengthy proof of the following result. Theorem 2.1. For a tree T and an integer k 1, the vertex u V (T ) is k -simple in T iff u is strongly simplicial in T k . 3 Inductiveness of outerplanar graphs In this section we will derive the optimal bound for the inductiveness of an outerplanar graph G of maximum degree 5. When 7 the inductiveness will also yield an optimal bound for both the clique number and the chromatic number. We will first assume G to be biconnected, in which case we can assume the vertices to be labeled {u1 , . . . , un } in a clockwise order along the infinite face of G. In this way the weak dual T (G) is a connected tree. Consider a maximal chain of consecutive degree-two vertices (ui , . . . , ui+ ) in G, viewed in clockwise order. For any u {ui , . . . , ui+ }, the first vertex to the left of u which has degree of three or more, is ui-1 . Likewise ui++1 is the first vertex to right of u which has degree three or more. Conventions: (i) For each such a degree-two vertex u, then we denote ui-1 by ul (l for "left") and we denote ui++1 by ur (r for "right".) (ii) The leaf of T (G) corresponding to the face f of G will be denoted by f and will be called the dual vertex of f . Likewise if a degree-two vertex u of G is on a boundary of a face corresponding to a leaf in T (G), then we denote that face by fu and the corresponding leaf of T (G) by fu , and will call it the dual vertex of u. Note that when G is chordal and u is a degree-two vertex, then ul and ur are the left and right neighbors of u in G respectively and they are connected. bounding the infinite face of G, then fui = fui+1 = · · · = fui++1 all represent the same leaf of T (G). Our first goal in this section is to prove the following theorem. Theorem 3.1. Let G be a biconnected outerplanar graph with maximum degree 5. Let f be a face of G, whose dual vertex f is strongly simplicial in T (G)2 . 1. If f has no sibling in T (G), then f contains a degree-two vertex on its boundary with at most +1 neighbors in G2 . 2. If f has a sibling g in T (G), then either f or g contains a degree-two vertex on their boundary which has at most + 1 neighbors in G2 . In particular we have ind(G2 ) + 1. Before proving Theorem 3.1, we shall make some observations and prove a lemma. Recall that since G is a plane graph, then so is the dual tree T (G). If there is a leaf f of T (G) such that f is bounded by a cycle of length five or more in G, then there is a degree-two vertex with both its neighbors of degree two, and hence its degree in G2 is four or less. We will therefore henceforth assume that each face corresponding to a leaf in T (G) is bounded by a cycle of length three or four. Suppose we have leaves f1 , . . . , fp , where p 3, which are all siblings, and where their listing is clockwise w.r.t. their common parent in the plane embedding of T (G). In this case each degree-two vertex bounding the internal faces f2 , . . . , fp-1 has degree at most six in G2 , since its neighbors have at most degree four in G. Hence their degree in G2 is also at most six. We will therefore henceforth assume that every leaf in T (G) has at most one sibling. Convention: For an arbitrary plane tree T , and a leaf x of T , denote by l x and r x the left and right neighbor leaves of x respectively, in a clockwise preorder traversal of the vertices of T . Denote by l (x) and r (x) the distances in T from x to l x and r x respectively. Lemma 3.2. Let G be a biconnected outerplanar graph Claim 3.1. A plane biconnected outerplanar graph G of maximum degree 3 and let u be a degree-two of maximum degree 3 has at least two degree-two vertex u in G such that fu is a leaf in T (G). In this vertices u and v , such that both fu and fv are leaves in case we have the weak dual tree T (G). (3.1) dG (ul ) l (fu ) + 2, Remark: Unlike the chordal case, where we have the (3.2) dG (ur ) r (fu ) + 2. one-to-one correspondence u u , the correspondence here u fu is not unique, since if a face f correspond- In particular, nl = |N [ul ]| l (fu ) + 3 and nr = ing to a leaf f , is bounded by ui-1 , ui , . . . , ui+ , ui++1 |N [ur ]| r (fu ) + 3. Equality holds in (3.1), and hence where the edge {ui-1 , ui++1 } is the only edge not also for nl , iff ul = vr for some degree-two vertex v 247 exactly three vertices. Since the degree of f in T (G) is three, there are exactly three edges on the boundary of f which do not face the infinite face, two of them being {ul , ur } and {vl , vr }. If f is bounded by four or Proof. The simple path in T (G) from fu to l fu has more vertices, then there is an edge with either ul or length at least dG (ul ) - 2. The length is precisely vr as an endvertex, bounding f and the infinite face, dG (ul ) - 2 iff ul = vr for some degree-two vertex on say ul . In this case dG (ur ) = 4 and dG (ul ) = 3 and the boundary of l fu . In the same way we obtain the hence u has at most five neighbors in G2 . Therefore we result for fr . T can assume f to be bounded by exactly three vertices, which in this case must consist of ul , ur = vl and vr . he following proof of Theorem 3.1 consists of dispatch- Since f is a leaf of T (G)(1) , then by Lemma 3.2 we ing several cases, treating the most involved case last. have nr 5, and further we have nl + 1. Since now N [ul ] N [ur ] = {u, ul , ur , vr }, we finally have by Proof. (Theorem 3.1) Let f be a leaf which is strongly the I/E principle that simplicial in T (G)2 , and let u be a degree-two vertex on the boundary of the corresponding face f . In this d (u) = |N [u ] N [u ]| - 1 = (n + n - 4) - 1 + 1, 2 l r l r case f = fu . If f has no sibling, then either ul or ur has degree which completes the proof of the theorem. W three, say dG (ur ) = 3, in which case nr = 4. If f is bounded by four vertices, then the degree-two hen 7 we can obtain sharper results. The neighbor of ur has at most four neighbors in G2 . If f is underlying reason for this is that when 7, then bounded by three vertices, then for the unique degree a f two vertex u bounding f we have nr = 4, nl + 1 T (G) has a p th o2)length five or more, and hence the pruned tree T (G)( is proper with leaves. and {u, ul , ur } N [ul ] N [ur ], and hence by the Let f be a leaf in T (G). As mentioned, we can inclusion/exclusion (I/E) principle we obtain assume that corresponding face f is bounded by three or four vertices. We can further assume that f has (3.3) d2 (u) = |N [ul ] N [ur ]| - 1 at most one sibling. The next lemma shows that we = (nl + nr - 3) - 1 + 1. can make the same assumption for the parent f of If f has a sibling g (which we can assume is to the f . Recall that for a group of three or more siblings, right of f in the planar embedding of T (G)), let v a leaf is internal if it has at least one sibling to its left be a degree-two vertex on the corresponding face g , and another to its right, when viewed from the their and hence in this case g = f . Since f and g are common parent in the plane embedding of T (G). strongly simplicial in T (G)2 , then by Proposition 2.1 their common parent f = g = fu = fv is a leaf in (1) the pruned tree T (G) , which is proper since 5. All the vertices ul , ur , vl , vr are on the boundary of f , in this clockwise order. Note that both ur and vl are bounding at most three faces f , g and f , and therefore both of them have degree at most four. We now consider some cases. First case: ur and vl are distinct. In this case we have dG (ur ) = dG (vl ) = 3 and hence |N [ur ]| = |N [vl ]| = 4. If either f or g are bounded by four vertices, say f , then the degree-two neighbor vertex of ur has four neighbors in G2 . If both f and g are bounded by exactly three vertices, ul , u, ur and vl , v , vr respectively, then since {u, ul , ur } N [ul ] N [ur ] we obtain (3.3) by the I/E principle, as for the case where f had no sibling. Second case: ur = vl . In this case we have dG (ur ) = dG (vl ) = 4. If either f or g are bounded by four vertices, say f , then the degree-two neighbor of ur has at most five neighbors in G2 . We will for the rest of this proof assume that both f and g are bounded by v bounding l fu . Similarly, equality holds in (3.2), and hence also for nr , iff ur = wl for some degree-two vertex w bounding r fu . Lemma 3.3. Assume G is a biconnected outerplanar graph with maximum degree 7. Let f be a leaf which is strongly simplicial in T (G)3 . Assume that its parent f is an internal one among its three or more siblings in T (G)(1) . Then for any degree-two vertex u bounding f we have |N [ul ]| = nl 7 and |N [ur ] = nr 5, or vice versa. Proof. By Proposition 2.1 the common parent f of the siblings is a leaf in T (G)(1) . Hence if f has a sibling, then l (fu ) 4 and r (fu ) 2 or vice versa, and the lemma follows from Lemma 3.2. If f has no sibling we have further that either dG (ul ) = 3 or LG (ur ) = 3. d et f be strongly simplicial in T (G)3 . By Lemma 3.3 we can assume nl 7 which is the same as dG (ul ) 6. Treating dG (ul ) as the maximum degree, we can now apply exactly the same arguments as in the proof of Theorem 3.1 and obtain the following observation. 248 Observation 3.4. Let G be a biconnected outerplanar graph with maximum degree 7. Let f be a face of G, whose dual vertex f is strongly simplicial in T (G)3 , and assume further that its parent f is an internal sibling of three and more siblings in T (G)(1) . Then we have the fol lowing. 1. If f has no sibling in T (G), then f contains a degree-two vertex on its boundary with at most seven neighbors in G2 . 2. If f has a sibling g in T (G), then either f or g contains a degree-two vertex on their boundary which has at most seven neighbors in G2 . When consider the inductiveness of G2 for a biconnected graph G of maximum degree 7, we can by Observation 3.4 assume further that every leaf f has at most one sibling in T (G)(1) , in addition to assuming that each leaf face f is bounded by three or four vertices and that f has at most one sibling. Call such a G restricted, if it satisfies all these mentioned assumptions. In this case, we prove the following theorem. Theorem 3.2. Let G be a restricted biconnected outerplanar graph with maximum degree 7. Let f be a face, whose dual vertex f in T (G) is a leaf which is strongly simplicial in T (G)3 . Then one of the fol lowing holds: 1. f has a sibling g and either f or g contains a degree-two vertex on their bounding cycle, which has at most seven neighbors in G2 . g to be bounded by exactly three vertices v , vl and vr , where vl = ur , dG (vl ) = 4 and dG (vr ) = 6, where ul and vr are not connected, since f is bounded by at least four vertices. In this case, however, dG (ul ) = 3 must hold, since the degree of f in T (G) is exactly three and hence there are precisely three edges on the boundary of f which do not face the infinite face. By Lemma 3.2 we have dG (ur ) 4, and hence u has at most six neighbors in G2 . This proves the first part of three. Assume next that f has no sibling. In this case either dG (ul ) or dG (ur ) is three, say dG (ur ) = 3. If f is bounded by four vertices, then the degree-two neighbor of ur has at most four neighbors in G2 . Otherwise f is bounded by three vertices u, ul and ur . The only possibility for u to have more than neighbors in G2 , is for ul and ur to have only u as a common neighbor and dG (ul ) = . In this case f is bounded by at least four vertices, and there is a degree-two neighbor w of ur on the boundary of f , whose other neighbor (to its right) is either another degree-two vertex, in which case w has at most four neighbors in G2 , or a vertex u which is a neighbor of ul , where w, u , ul , ur are precisely the bounding vertices of f . Since f is strongly simplicial in T (G)3 , then by Proposition 2.1 the parent f of f is a leaf in the pruned tree T (G)(2) . From this we see that dG (u ) 6. In addition f has no siblings and therefore we have further that dG (u ) 5. Since u N [ur ] N [vl ]|, d2 (w) = |N [ur ] N [u ]| - 1 4 + 5 - 1 - 1 = 7, c 2. f has no sibling and its parent f is bounded showing that f ontains a degree-two vertex on its by three edges, in which case f contains a degree- boundary with at most 7 neighbors. This proves B two vertex on its bounding cycle with at most the theorem. 2 neighbors in G . y Observation 3.4 and Theorem 3.2 we obtain the 3. f has no sibling and its parent f is bounded by following corollary. four or more vertices, in which case either f or Corollary 3.1. For a biconnected outerplanar graph f contains a degree-two vertex with at most seven G with maximum degree 7, we have ind(G2 ) = . neighbors in G2 . So far we have only discussed the case where G is Proof. Let u be a degree-two vertex in G, whose dual a biconnected and outerplanar, and we have given a vertex fu = f is a leaf which is strongly simplicial complete description on how to locate the simplicial in T (G)3 . By Proposition 2.1 the parent f of f in vertices of G2 , in terms of the corresponding weak dual T (G) is a leaf in the pruned tree T (G)(1) , which we tree T (G) and the strongly simplicial vertices of its can by Observation 3.4 assume to be one of at most two second or third power, depending whether we consider siblings. If f has a sibling then assume it to be to the the case 5 or 7. right of f viewed from their common parent in the For a biconnected outerplanar graph G with maxplane embedding of T (G). imum degree 5 we have that the proper tree Assume f has a sibling g = r f to its right, T (G)(1) has at least two leaves. We have derived the which then is also strongly simplicial in T (G)3 . Since existence of degree-two vertices with at most + 1 l (g ) = 2 and r (g ) 4, we have by Lemma 3.2 neighbors in G from just one leaf of T (G)(1) . We can of that the only possibility of g not to contain a degree- course obtain another such degree-two vertex by worktwo vertex with at most seven neighbors in G2 , is for ing from another leaf of T (G)(1) . Likewise, if 7 249 we have that T (G)(2) is a proper tree with at least two leaves. From the proof of Theorem 3.2 we note that if f is a leaf of T (G) satisfying condition 3, where its parent f is the face containing the degree-two vertex w with at most seven neighbors in G2 , then the other degreetwo vertex with at most neighbors in G2 is clearly of distance three or more from w in G, since the degree two vertices of distance two form w are on the boundary of faces that correspond to leaves of T (G) which are descendants of f , the grandparent of f . In this case G2 has two simplicial degree-two vertices of distance three or more from each other. Assume that all the simplicial degree-two vertices of G2 , where G has a maximum degree 5, are of distance two from each other in G. If they are more than three, then clearly for any vertex x of G there is one simplicial vertex of in G2 of distance two or more from x in G. If however, there are only two simplicial vertices in G2 and they are of distance two from each other in G, then from the above, they must each be on the boundary of distinct faces f and h where f and h are strongly simplicial in T (G)3 (or in T (G)2 in case 6.) If now f and h are endpoints of a longest path in T (G), then both f and h are strongly simplicial in T (G)k for any k 2, in particular for k = 2, 3. By considering their possible siblings we may assume that these faces f and h contain the two degree-two vertices x and y which are simplicial in G2 , that is, have at most neighbors in G2 (or + 1 neighbors in the case 6.) Since there is a path in T (G) of length - 2, the distance between f and h is at least - 2. If z is the common neighbor of x and y in G, then there is a path between f and h of length dG (z ) - 2, but by the our choice of f and h we have dG (z ) = . From this we can deduce the following lemma. If the cut-vertex x is the neighbor of both the simplicial vertices x and y of B , then dB (x), dB (y ) (B ) (or (B ) + 1 if (B ) 6,) and hence both x and y have at most neighbors in G2 , since NG [x] induces a ( + 1)-clique in G, in the same way as NB [x] induces a clique of size (B ) + 1 in B . From this we obtain the main result of the paper. Theorem 3.3. For an outerplanar graph G of maximum degree 5, we have ind(G2 ) +1. If further, 7, then ind(G2 ) = . Cho osability and algorithmic concerns. As mentioned in the introduction, the bound on the inductiveness of Theorem 3.3 implies that Greedy finds an optimal coloring of squares of outerplanar graphs of degree 7. When < 6, we can also obtain an efficient time algorithm from the observation of Krumke, Marathe and Ravi [14] that squares of outerplanar graphs have treewidth at most 3 - 1. This allows for the use of 2O(k) n time algorithm for coloring graphs of bounded treewidth. Theorem 3.4. There is a linear time algorithm to color squares of outerplanar graphs. We conclude this section with an application of our results on inductiveness to choosability. Definition 3.6. A graph G is k -choosable, if for every col lection or lists {Sv : v V (G)} of colors, Sv {1, 2, 3, . . .} where |Sv | = k for every v V (G), there is v a color assignment c : V (G) V (G) Sv , such that · c(v ) Sv for each v V (G), and · if c(v ) = c(u) then v and u are not neighbors in G. The minimum such k is cal led the choosability or the list-chromatic number of G, and is denoted by ch(G). Lemma 3.5. In a biconnected outerplanar graph G with maximum degree 5, we have either of the two Note that if a graph is k -choosable, then it is k conditions. colorable. Also, by an easy induction, we see that if a 1. For any vertex x there is a simplicial vertex u of graph is k -inductive then it is (k + 1)-choosable. For any G2 of distance two or more from x in G. graph G we therefore have (G) ch(G) ind(G) + 1 and hence the following. 2. There is a vertex x such that the only two simplicial 2 vertices of G have x as a common neighbor in G Corollary 3.2. For any outerplanar graph with maxwhich is of degree in G. imum degree 7, we have ch(G2 ) = + 1. Let now G be a general outerplanar graph of maximum degree 5, and let B be a block which corresponds 4 Characterizations for the small degree case to a leaf of the block-cutpoint tree BC(G). Here B We conclude by characterizing bounds on the clique contains only one cut-vertex x. number, chromatic number and inductiveness for the If there is a simplicial vertex u of B 2 of distance two squares of outerplanar graphs of maximum degree or more from x, then u is also a simplicial vertex of G2 {2, 3, 4, 5, 6}. In the case of clique and chromatic with at most neighbors in G2 (or + 1 neighbors if number, we may assume by Lemma 2.1 that the graphs 6.) are biconnected. We start with the chordal case. 250 Proof. Clearly each graph in {F4 } {RLn : n 5} is biconnected and outerplanar. Conversely, let G be a V (RLn ) = {u1 , . . . , uk } {v1 , . . . , vk }, biconnected outerplanar graph on n 5 vertices with E (RLn ) = {{ui , vi }, {ui , ui+1 }, {ui , vi+1 }, {vi , vi+1 } : maximum degree four. By removing a vertex u of degree i {1, . . . , n - 1}} {{uk , vk }}. two from G, we obtain a biconnected outerplanar graph G-u with (G-u) {3, 4}, and hence equal to RL4 or, For odd n, the graph RLn will mean RLn+1 - u(n+1)/2 . by induction, from the set {F } {RL : n 5}. Since 4 n K G is of maximum degree = 4 it is impossible that (iii) Let F4 = K3 , F5 = RL4 , and F6 = 3 . We characterize exactly the chromatic and clique G - u = F4 . For the same reason if G - u = RL4 , then numbers of squares of chordal outerplanar graphs in G = RL5 . Also, G-u = RL5 only when G {RL6 , F4 }, and lastly if G - u = RLn for some n 6, then terms of forbidden subgraphs F . N = RLn+1 must hold, thereby proving the lemma. G Theorem 4.1. Let G be a chordal outerplanar graph of ote that for G = F4 we have G2 = K6 . Hence both maximum degree . Then, (G2 ) and (G2 ) equal + 2 = 6, while ind(G2 ) = 5. 2 1. (G ) = + 1, unless {4, 6} and F G in Observe that ind(RL2 ) = 4, for any n 5, since n 2 which case (G ) = + 2. removing the last vertex in the square graph leaves the graph RL2 -1 . Thus, (RL2 ) = (RL2 ) = 5. By n n n 2. (G2 ) = + 1, unless = 4 and F G in which Lemma 2.1 we have proved Theorem 4.1 for = 4. 2 case (G ) = + 2. The last two cases to consider are {5, 6}. For these we provide optimal bounds of (G2 ) and (G2 ) We consider each maximum degree separately in terms of the maximum degree . The proof of the following lemma is omitted. (with > 6 treated in the preceding section.) The case = 2 is trivial since there is only one chordal Lemma 4.4. Let G be a chordal biconnected outerplaouterplanar biconnected graph G = K3 . The case nar graph with such that the dual tree of G is ful l. If 3 is easy, since there are only three biconnected {5, 6}, then G = F . chordal outerplanar graphs with 3: RL2 = P2 , the 2-path, RL3 = C3 = K3 , the 3-cycle, and RL4 is Note that F5 has = 5, and there are exactly two the 4-cycle with one diagonal. From this we deduce the disjoint pair of vertices of distance 3 from each other. following tree-like structure of G in this case. Each pair can form a monochromatic pair in the square of F5 , and the remaining vertices can receive a unique Lemma 4.1. Let G be a chordal outerplanar graph of 2 color, which shows that (F5 ) = 6. We shall use the maximum degree 3. Then the blocks of G are following definition. among {RL2 , RL3 , RL4 }, where any two blocks from {RL3 , RL4 } are separated by at least one RL2 block. Definition 4.5. Let G be a graph. Cal l a subgraph Considering the blocks of G that represent the leaves H G on h vertices an h-separator, or just a separator 2 2 in the block cut-point tree BC(G) we obtain from the if it induces a clique in G whose removal breaks G into disconnected components. structure given in Lemma 4.1 the following. The following lemma shows that it suffices to bound Observation 4.2. For a chordal outerplanar graph G with {2, 3}, we have (G2 ) = (G2 ) = ind(G2 ) + the chromatic number for graphs without separators. 1 = + 1. Lemma 4.6. If a graph G has a separator H with G and H = G G , then (G2 ) = The case = 4 is more interesting, since it is the G = G 2 2 first case involving a "forbidden subgraph" condition for max{(G ), (G )}. Conventions: (i) Let G be a given biconnected outerplanar on n vertices of maximum degree , with a fixed planar embedding. The graph obtain from G by connecting an additional vertex to each pair of endvertices of an edge bounding the infinite face, will be denoted by G. Clearly G will be an outerplanar graph on 2n vertices of maximum degree + 2. (ii) By the rigid n-ladder or just the rigid ladder RLn on n = 2k vertices we will mean the graph given by both the clique and the chromatic number of G2 . By considering the removal of a degree-two vertex from G, we obtain the following by induction on n, the number of vertices of G. Lemma 4.3. A graph G is a biconnected chordal outerplanar graph with = 4 if, and only if, G {F4 } {RLn : n 5}. 251 For = 2, we give a complete characterization, albeit not very compact. Let Pk (Ck ) be the path (cycle) on k vertices, respectively. It can be verified that e note that if the dual tree T (G) is not full, then 3 G = Pk C3k G contains a ( + 1)-separator. This separator is in 4 G = C3k+1 C3k+2 \ C5 (G2 ) = fact induced by the neighborhood of a single vertex. By 5 G = C5 Lemma 4.4 we have proved Theorem 4.1 for = 5, 6. For the clique number we have the following. 3 otherwise 4 G = C4 (G2 ) = Lemma 4.7. For an outerplanar graph G with 5, 5 G = C5 we have (G2 ) = + 1. Further, any clique with + 1 2 G = Pk C3 vertices is the closed neighborhood of some vertex. 3 G = C4 ind(G2 ) = 4 G = Ck , k 5. Proof. We show that the only way to form a clique on 6 vertices in an outerplanar graph is via the closed Further, Greedy obtains an optimal coloring even when neighborhood of a vertex. inductiveness is not a tight bound on the chromatic Consider an induced subgraph St of G with t + 1 number. vertices: a vertex u and its neighbors u1 , u2 , . . . , ut in For = 3, consider the graph G consisting of C5 a clockwise order in the plane embedding of G. Then with an additional chord. Then, ind(G2 ) + 1 = (G2 ) = only adjacent pairs ui and ui+1 , for i = 1, . . . , t - 1, may (G2 ) = + 2 = 5. For = 4, the graph G = C4 be connected by an edge. Consider now a vertex w that satisfies ind(G2 ) = + 2 = 6. Other lower bounds is not a neighbor of u. Then, w can be adjacent to at follow from the chordal case. most two neighbors of u and only consecutive ones, by We now turn to upper bounds in the non-chordal the outerplanarity property. Then, if t 5, w cannot case. Recall the upper bounds on ind and given by be adjacent to both one of u1 and u2 and to one of ut-1 Theorem 3.1 and Lemma 4.7 for 5. The following and ut . Thus, it must be of distance at least 3 from two results fill all the remaining gaps, but one. either u1 or ut . Hence, S {w} is not a clique. Consider instead when t = 4 and we have two Lemma 4.9. If G is an outerplanar graph with maxivertices w1 and w2 that are non-neighbors of u. In mum degree = 4, then (G2 ) 6. order to be of distance at most 2 from both u1 and u4 , a vertex must be adjacent to u2 and u3 . But, in Proof. By Lemma 2.1 we may assume G to be biconan outerplanar graph, not both w1 and w2 can be so. nected. By induction on n, we may assume that each face f corresponding to a leaf f of the dual tree T (G) Hence, S4 {w1 , w2 } does not form a clique. Finally, suppose an induced subgraph H of max- is bounded by exactly three vertices, since otherwise imum degree three induces a 6-clique in G. By there is a degree-two vertex on f with at most + 1 = 5 2 Lemma 2.1 we can assume H to be biconnected. There neighbors in G . Let u, v , w be the three vertices boundcan be at most two chords in H and they must be dis- ing f , where u is of degree 2. Then we can further asjoint since (H ) = 3. Then there are two vertices in sume that we always have dG (v ) = dG (w) = 4, since 2 H of degree two that are of distance 3 in H . Further, otherwise u has at most five neighbors in G also in since all vertices of H lie on the outer face, there can this case. Now, by contracting u, v , w into a single verbe no vertex outside H connecting them. Hence, the tex, the same assumptions hold for the resulting graph. Hence, by induction on n = |V (G)|, we see that G must lemma. U have the form G = Cn for some n 3. 2 2 4 sing F4 , F5 and F6 as building blocks, we can Since Cn C2n , we have Cn C2n , which can be obtain the following (proof omitted). colored cyclically in a greedy fashion by colors 1 through 2 5, or 1 through 6. Hence, (Cn ) 6, which completes Observation 4.8. For each {4, 5, 6}, there are T e proof. th infinitely many biconnected chordal outerplanar graphs 2 G of maximum degree with ind(G ) = + 1. he proof shows that when G is biconnected with = 4, then G2 is 5-inductive unless G = Cn , for some Non-chordal graphs of small degree. Non- n 3. chordal graphs become quickly harder to characterize. We illustrate first the instances of non-chordal graphs Lemma 4.10. If G is an outerplanar graph with maxithat give higher values than for chordal graphs. mum degree = 3 or = 4, then ind(G2 ) 2 - 2. Proof. Since G2 = G 2 G 2 and G 2 G which is a clique, we have the lemma. W 2 = H 2, 252 Proof. Proof by induction on the number n of vertices. The base case is immediate. We show that there exists a degree-two vertex with at most 2 - 2 neighbors in G2 . Contracting an edge incident to this vertex yields a graph on n - 1 vertex of maximum degree at most . By the inductive hypothesis, this graph is 2 - 2-inductive, thus yielding the same for G2 . Consider a face f of G whose dual vertex is a leaf of T (G). If f is bounded by a 5-cycle or larger, then there is a degree-two vertex whose neighbors are also of degree 2. Hence, the degree of that vertex in G2 is 4 2 - 2. If f is bounded by a 4-cycle, then there are two adjacent degree-two vertices on the cycle, and both of them have + 1 < 2 - 2 neighbors in G2 . Finally, if f is bounded by a 3-cycle, then the degree-two vertex A the cycle has at most 2 - 2 neighbors in G2 . on s a corollary, (G2 ) (G2 ) + 2 = 5 when = 3. The case of the chromatic number of squares of nonchordal outerplanar graphs when = 5 remains open; we conjecture that it is always + 1 = 6. Acknowledgments The authors are grateful to Steve Hedetniemi for his interest in this problem and for suggesting the writing of this article. References [1] G. Wegner. Graphs with given diameter and a coloring problem. Technical report, University of Dortmund, 1977. [2] T. R. Jensen and B. Toft. Graph Coloring Problems. Wiley Interscience, 1995. http://www.imada.sdu.dk/Research/Graphcol/. [3] G. Agnarsson, M. M. Halld´rsson, Coloring Powers of o Planar Graphs, SIAM Journal of Discrete Mathematics, to appear. [4] P. Duchet. Propri´t´ de Hel ly et Probl´mes de ee e Repr´sentation, Col loque C.N.R.S., (Orsay 1976), e CNRS, Paris, 260:117­118, 1978. [5] R. Balakrishnan and P. Paulra ja. Powers of Chordal Graphs, Australian Journal of Mathematics Series A, 35:211-217, 1983. [6] G. Agnarsson, R. Greenlaw, and M. M. Halld´rsson. o On Powers of Chordal Graphs and Their Colorings, Congressus Numerantium, 144:41­65, (2000). [7] R. Laskar and D. Shier. On Powers and Centers of Chordal Graphs, Discrete Applied Mathematics, 6:139­147, 1983. [8] D. B. West, Introduction to Graph Theory, PrenticeHall Inc., 2nd ed., 2001. [9] R. C. Read. An Introduction to Chromatic Polynomials, J. of Combinatorial Theory, 4, 52­71, 1968. [10] R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford University Press, 1998. [11] N. Kalyana Rama Prasad and P. Sreenivasa Kumar. On generating strong elimination orderings of strongly chordal graphs, FSTTCS '98, Lecture Notes in Comput. Sci.,1530: 221­232, Springer, Berlin, 1998. [12] D. G. Corneil and P. E. Kearney. Tree Powers, Journal of Algorithms, 29:111­131, (1998). [13] H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6):1305­1317, 1996. [14] S. O. Krumke, M. V. Marathe, and S. S. Ravi. Approximation algorithms for channel assignment in radio networks. Dial M for Mobility, 1998. [15] X. Zhou, Y. Kanari, and T. Nishizeki. Generalized vertex-colorings of partial k-trees. IEICE Trans. Fundamentals, E83-A:671­678, 2000. [16] M. Molloy and M. R. Salavatipour. A bound on the chromatic number of the square of a planar graph. At CiteSeer. Earlier version appears in ESA 2001. [17] O. Borodin, H. J. Broersmo, A. Glebov, and J. van den Heuvel. Colouring at distance two in planar graphs. In preparation, 2001. 253