Informatica 30 (2006) 321-324 321
Coloring Weighted Series-Parallel Graphs
Gasper Fijavz
Faculty of Computer and Information Science E-mail: gasper.fijavz@fri.uni-lj.si
Keywords: graph coloring, circular coloring, weighted graphs Received: December 31, 2003
Let G be a series-parallel graph with integer edge weights. A p-coloring of G is a mapping of vertices of G into Zp (ring of integers modulo p) so that the distance between colors of adjacent vertices u and v is at least the weight of the edge uv. We describe a quadratic time p-coloring algorithm where p is either twice the maximum edge weight or the largestpossible sum of three weights of edges lying on a common cycle.
Povzetek: Opisanoje barvanje grafov.
1 Introduction
The motivation of the problem is twofold. An instance of coloring edge weighted graphs is the channel assignment problem, cf. [4]. On the other hand, traditional vertex coloring of (unweighted) graphs can be viewed as a circular one—consider the colors to lie in an appropriate ring of integer residues. Circular colorings of graphs, see [8] for a comprehensive survey, where we allow the vertices to be colored by real numbers (modulo p) model several optimization problems better than traditional colorings of graphs. Circular chromatic number, the minimum p for which a circular coloring exists, is a refinement of the chromatic number of a graph, and similarly NP-hard to compute.
If the largest complete minor in (an unweighted graph) G has k vertices and k < 6, then the valid cases of Hadwiger conjecture imply x(G) < k, see [7].
Let G = (V,, E, w) be a weighted graph (where (V, E) is the underlying unweighted graph) with edge weights w (and w : E ^ [1, to)). We can, similarly as in the unweighted case, define the size of the largest complete minor, see [5, 6, 3]: the size of the largest weighted K2 -minor in G is twice the maximal edge weight, and for the size of the largest weighted complete K3 minor we have also to consider the biggest possible sum of weights of three edges lying on the common cycle. If G is a series parallel graph then the largest of the above-mentioned quantities is called the weighted Hadwiger number of G, which we denote by h(G).
The weighted case of Hadwiger conjecture is valid only for graphs satisfying h(G) < 4, i.e., it is true that if h(G) < 4, then the weighted chromatic number of G, which we denote by Xw (G), is at most h(G) [3]. If a weighted graph G is not series-parallel, then it may occur that xw (G) > h(G), see [3] for examples.
Hence, for series-parallel weighted graphs h(G) is a natural upper bound for xw (G). We present an algorithm for h(G)-coloring weighted series-parallel graphs. As op-
posed to results in [3], the coloring algorithm presented here successfully colors series-parallel graphs with at most h(G) colors even if the ratio between maximal and minimal edge weights exceeds 2.
2 Definitions and preprocessing
Let N denote the set of positive integers and let Zp denote the ring of integers modulo p. If x,y G Zp then we denote the distance between x and y in Zp by \x — y|p. Let G = (V, E, w) be a weighted series-parallel graph. Series-paralel graphs are constructed by first pasting triangles along edges (starting with a triangle), and then deleting edges [2]. In order to avoid computational difficulties concerning real numbers we shall assume that weights are integers, w : E ^ N. A p-coloring of G is a mapping c : V ^ Zp so that for every edge e = uv the condition
\c(u) — c(v)\p > w(uv)
is satisfied. Given a p-coloring c and an edge e = uv, we call \c(v) — c(u)\p the span of e, denoted by span(e), and say that e is tight if its span equals its weight. We shall also say that p is the size of the color space Zp.
2.1 Tree decomposition
Tree decomposition, see [2] for the theoretical background, of a series-parallel graph can be computed in lineartime [1]. Given a tree-decomposition (TG, V) of G we can by adding edges to G (and setting their weights to 1) assume that G is an edge-maximal series parallel graph. The parts V of the decomposition are exactly the edges and triangles of G. Two parts are adjacent (in TG) if and only if one part is a triangle t, the other is an edge e, and e is incident with t.
Hence, G is 2-connected, and given distinct edges e and f from G, there exists a cycle containing both. We shall
322 Informatica 30 (2006) 321-324
G. Fijavz
use both G and its tree decomposition (TG, V) for storing the graph during the course of the coloring algorithm.
Let e = v1v2 be an edge in G. If {v1,v2} is a separator in G we say that an edge e is a separating edge in G, and e is called nonseparating otherwise. If e = v1v2 is separating and G— {v1, v2} consists of k components C1,... ,Ck, then Gi (i = 1,... ,k) denotes the graph (infact its representation) induced by vertices of Ci and {vi, v2}. We call Gi's (i = 1,... ,k) the e-splits of G.
Throughout the algorithm we shall keep track whether an edge e is a separating edge of G. This can be easily seen from TG, namely, an edge e is nonseparating if it is adjacent to a single triangle in TG.
Let t = e1e2e3 be a triangle (t contains edges e1, e2, and e3) in G. Let us further assume that e1 is a separating edge and let G0, G1... ,Gk be all e1-splits of G, so that G0 contains triangle t as its subgraph. Then the (graph) union G1 U ... U Gk is called the (t, e1)-fragment of G and is denoted by G(t, e1). If e is nonseparating, and there exists a triangle t containing e (there may be at most one), then the (t, e)-fragment of G is the graph containing only e together with its endvertices. We call a graph trivial if it contains at most two vertices.
2.2 Heavy cycle, heavy triangle
As noted in the introduction h(G), the hadwiger number of G, equals either twice the weight of the heaviest edge or the sum of three largest edge weights of edges lying on a common cycle. It is the latter option that is more appealing to our problem.
Let t = f1f2f3 be a triangle in G. Define G1 = G(t,f1), G2 = G(t,f2), and G3 = G(t,f3). If Gi (i = 1, 2, 3) is trivial, then we say that ei = fi is a realizing edge of t (in Gi). If Gi is not trivial then every heaviest edge in Gi can be chosen as a realizing edge of t (in Gi). Weight of a triangle t, w(t), is defined as the sum of edge weights of edges realizing t. Clearly enough, the realizing edges of a triangle lie on a common cycle in G.
Let e1 and e2 be distinct edges with largest edge weights in G. Triangle t is called a heavy triangle if w(t) equals h(G), and both e1 and e2 are realizing edges of G. It may occur that no triangle is heavy in G. In this case we can by increasing weight of a single edge construct a heavy triangle in G while not increasing h(G). This is the essence of the procedure heavyTriangle described in the next section.
By scanning through the edges of G, we find some heaviest edge ea = uava. Next we run
heavyTriangle(G, ea, ea, ea) ^ h(G); t, fa, fb, fc; eb, ec, P.
Finally, we set p = h(G), c(ua) = 0, c(va) = w(ea) and run the main coloring procedure
color(G,p, t; fa,fb,fc; ea, eb, ec;
P)
using a heavy triangle t = fafb fc with its realizing edges ea, eb, and ec as arguments.
3 Coloring algorithm
The coloring algorithm is recursive. Given a graph G with two precolored adjacent vertices ua and va we split G along a carefully chosen edge(s) into several subgraphs, say G0, G1,... Only one of these, say G0, contains both ua and va, and it is the first one to get colored. We find colorings of G1,G2,... recursively, taking care that exactly two vertices of Gj are already colored when it is Gj 's turn.
3.1 Looking for a heavy triangle
We shall first describe the routine heavyTriangle. The input for his routine consists of weighted graph G, edges ea and eb (ea is heaviest in G, and eb is either second heaviest in G or ea = eb), and a path P C TG linking edges ea and eb (P is trivial in case ea = eb).
The routine heavyTriangle outputs, apart from the possibly new eb and P, also the hadwiger number h(G), a heavy triangle t = fa fb fc, and its third realizing edge ec. We set the notation so that ea e E(G(t, fa)), eb e E(G(t, fb)), and ec e E(G(t, fc)), and assume that h(G) = w(ea) + w(eb) + w(ec).
We use the following shorthand
heavyTriangle(G, ea, eb, P) ^ h(G); t, fa, fb, fc; eb, ec, P.
The routine runs as follows: (T1) if ea = eb then
we find some second heaviest edge in G and adjust P so that P links ea and the newly determined eb. Hence ea =
eb.
(T2) For every triangle t we compute the realizing edges and its weight w(t). This can be done by tracing TG starting from ea first. Hence ea is one of the realizing edges in every triangle t. By retracing towards ea from the leaves of TG we compute the other two realizing edges of every triangle recursively. Finally we set that eb is one of the realizing edges in every triangle lying in P (in the direction from eb to ea).
(T3) Find the triangle t' with largest possible w(t'). Set h(G) = max{w(t'), 2w(ea)}. (T4) If h(G) > w(t') or
h(G) = w(t') and eb is not one of the realizing edges of t' then do the following:
Let t = fafbfc be an arbitrary triangle from P so that ea
G(t, fa) and eb e G(t, fb). Set ec = fc and increase the
weight of ec = fc by setting w(ec) = h(G) — w(ea) —
w(eb). Note that increasing weight of ec does not increase
h(G), as ea and eb are heaviest edges in G.
(T5) If h(G) = w(t') and
eb is one of the realizing edges in t'
then :
By (T2) ea is also one of the realizing edges in t'. Set t = t'. Further, set ec to be the third realizing edge in t = fafbfc where the notation of edges in t is chosen so
that ea e E(G(t, fa)), etc.
COLORING WEIGHTED SERIES-PARALLEL GRAPHS
Informatica 30 (2006) 321-324 323
(T6) output h(G); t, fa, fb, fc; eb, ec; P.
It is not difficult to see that heavyTriangle runs in linear time.
3.2 Recursion
We shall first describe a routine for coloring a graph with small edge weights. Let e = uv be the heaviest edge in G, and assume that p > 3w(e), where p denotes the size of the color space. Let us also assume that colors c(u) and c(v) are already determined so that the span(e) is at most p -2w(e). Procedure colorCgraph with G, p, and e as its input (satisfying the above conditions) extends the coloring c to the remaining vertices of G. This can be done by tracing along Tg starting at e, and taking care that every edge f e G satisfies span(f) < p - 2w(e) (as w( f) < w(e)). It is easy to implement colorCgraph to run in linear time.
We turn our attention to coloring the graph in case its edge weights (at least some of them) are large when compared to h(G). Let G be a weighted graph, p an upper bound for h(G), t = fafbfc a heavy triangle, and ea, eb, and ec its realizing edges (so that ea e E(G(t, fa)), etc.). Let P be a path in TG joining ea and eb, and suppose that a coloring of endvertices of ea is given so that ea is tight. Then
Coloring Principle. With the assumptions as above the procedure color extends the coloring c to the rest of G so that
(i)	apart from ea the edge eb is also tight, and
(ii)	span(ec) < p - w(ea) - w(eb). The call
color(G,p,t; fa, fb,fc, ea, eb, ec; P)
splits into three cases, and exactly one of them applies. These three cases will also serve as a recursive proof that a graph can indeed be colored according to the principle. The first case (C1) serves as the recursion basis, the last two cases (C2) and (C3) serve as recursion steps. (C1) if G contains a single triangle t then. In this case ea = fa, eb = fb, and ec = fc. Let u and v be the (colored) endvertices of ea, and let w be the common endvertex of eb and ec. There exists a unique color c(w) so that eb is tight and span(ec) = p - w(ea) - w(eb). Hence, we can extend the coloring to G according to the coloring principle. exit
(C2) if ea is a separating edge in G then
let G0,Gi,... ,Gk be the ea-splits of G so that G0 contains
eb, ec, fa, fb, fc, t, and P. We first color G0 by calling
color(Go,p,t; fa,fb, fc, ea, eb, ec;
P)
and then take care of the other splits: for i = 1 to k do heavyTriangle(Gj,p,ea,ea,ea) ^
h(Gi ) ,ti; fai, fbi, fci ; ebi, eci, Pi
for i = 1 to k do
color(Gi, p, ti; fai, fbi, fci; ea, ebi, eci; Pi) exit
(C3) if ea is nonseparating in G then
we first increase weights of fb and fc by setting w(fc) =
w(ec) and w(fb) = w(eb).
Let Ga be the graph containing G(t, ea) and triangle t. Observe that either Ga contains at least two triangles or at least one of G(t, fb), G(t, fc) is not trivial (i.e. at least one of fb, fc is separating in G). Let Pa be the subpath of P linking fb and ea. Since w(fb) = w(eb) the edge fb is second heaviest in Ga. if ea = fa then
color(Ga,p,t; e a , fb , fc ; e a , fb , fc ; Pa ) Note that in the above case Ga contains a single triangle t as ea is not separating in G. else
Observe that w(fa) < w(eb) = w(fb), as eb is second heaviest in G and ea = fa. Hence, we increase the weight by setting w(fa) = w(fb), which makes fa second heaviest in G(t, fa). Let P' be the subpath of Pa linking ea and fa, let G' be the graph G(t, fa), and let G" be the subgraph of G induced by triangle t. heavyTriangle(G',p,ea,fa,P') ^
h(G'),t'; fa,f',fc; fa,e'c,P' color(G',p,t'; fa, f ',fc; ea,fa,e'c; P') After coloring G' the edge fa is tight and we also
color (G'',p,t; fa , f , fc ; fa , f , fc ; fa tf ) end if
Note that at this point endvertices of both f and fc are colored. What is more, f is tight, and by recursion,
span(fc) < p - w(ea) - w(fb) = p - w(ea) - w(eb).
Finally we settle the uncolored parts. if fb is separating in G then heavyTriangle(G(t, fb), fb, eb, ebPfb) ^ h(G(t, fb)),ti; fai, fbi, fd; ebi,ed,Pi color(G(t, fb),p, ti; fai, fbi, fci; fb, ebi, eci; Pi) if fc is separating in G then
colorCgraph(G(t, fc),p, fc) exit
4 Time complexity
The last section is devoted to estimating the speed of the coloring algorithm.
Time complexity. There exists a constant C so that for every weighed series parallel graph G of order n, the running time of the described coloring algorithm is bounded above by Cn2. In other words, we can h(G)-color a weighted series parallel graph G in quadratic time.
As already mentioned, the preprocessing takes linear amount of time. After preprocessing G is an edge maximal series parallel graph. If G contains n + 3 vertices then G contains n triangles, 2n +1 edges, and 3n lines (edge-
324 Informatica 30 (2006) 321-324
G. Fijavz
triangle incidencies). All these quantities are equally appropriate for measuring the size of the problem.
Let T(n) denote the maximal running time for the color procedure taking a graph G with n triangles as an input. We have to show that T(n) < Cn2 assuming T(m) < Cm2 for every m < n.
Let D0n be the upper bound for the running times of both heavyTriangle and colorCgraph if they take agraph G containing n triangles as input.
A call of color with G as its argument takes one of the three possible options: (C1), (C2), or (C3). The running time of (C1) is bounded above by a constant, say Di.
If (C2) applies let G0,G1,... ,Gk be the splits. Observe that k > 1. Since Gj's together contain exactly n triangles, the recursively called procedures heavyTriangle cumulatively take no more than D0n running time.
Let (n0, n1, n2,..., nk) be a proper (integer) partition of n, i.e. no,ni,n2,... > 1, k > 1, and no + ni + • • • + nk = n. Then
n0 + n\ + ••• + n2k < n20 + (ni + ••• + nk )2 < (n - 1)2 + 1
(1)
Now (1) implies that the cumulative running time of recursive calls of procedure color in (C2) is bounded from above by C(n - 1)2 + C. Summing it all up, the running time of (C2) is bounded from above by C(n-1)2 +C+D0n+D2n if we use at most D2n time for running the loops (excluding time for recursive calls of heavyTriangle and color).
The case when (C3) applies is settled similarly as above. Assume that the base running time of (C3) (i.e. the running time excluding running times of recursive calls of color, colorCgraph, and heavyTriangle) is bounded by constant D3. Recursive color-ing and colorCgraph-ing takes at most C(n-1)2 + C, and heavyTriangle-s takeatmost D0n time. Combining all three possibilities yields T(n) < max{D1, C(n - 1)2 + C + D0n + D2n, C(n - 1)2 + C + D0n + D3} < max{D1; Cn2 + (-2Cn + 2C + D0n + D2n), Cn2 + (-2Cn + C + D0n + D3)},
which is, if C is large enough, at most Cn2. This proves the assertion on time complexity.
Acknowledgment
The author's research was conducted while visiting University of Hannover under sponsorship of Alexander von Humboldt Foundation. Both hospitality of the university and help of the foundation are greatly acknowledged.
References
[1]	H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Com-put., 25(6):1305-1317, 1996.
[2]	R. Diestel. Graph theory. Springer, New York, 1997.
[3]	G. Fijavz. Hadwiger's conjecture for circular colorings of edge-weighted graphs. Discrete Math., to appear.
[4]	C. McDiarmid. Discrete mathematics and radio channel assignment. In Recent advances in algorithms and combinatorics, volume 11 of CMS Books MathJOuvrages Math. SMC, pages 27-63. Springer, New York, 2003.
[5]	B. Mohar. Circular colorings of edge-weighted graphs. J. Graph Theory, 43:107-116, 2003.
[6]	B. Mohar. Haj6s theorem for colorings of edge-weighted graphs. Combinatorica, 25:65-76, 2004.
[7]	B. Toft. A survey of Hadwiger's conjecture. Congr. Numer., 115:249-283, 1996. Surveys in graph theory (San Francisco, CA, 1995).
[8]	X. Zhu. Circular chromatic number: a survey. Discrete Math., 229(1-3):371-410, 2001. Combinatorics, graph theory, algorithms and applications.