On Distance Coloring

Dexter Kozen∗ Cornell University

Alexa Sharp† Oberlin College

June 29, 2007

Abstract
Call a connected undirected graph (d, c)-colorable if there is a vertex coloring using at most c colors such that no two vertices of distance d or less have the same color. It is well known that (1, 2)-colorability is decidable in linear time, but (1, c)-colorability for c ≥ 3 is NP -complete. In [19], Sharp shows that for fixed d ≥ 2, the (d, c)-colorability problem is solvable in linear time for c ≤ 3d/2 and NP -complete otherwise. In this note we give an alternative construction that improves the upper time bound as a function of d for the case c ≤ 3d/2. The construction entails a generalization of the notion of tree decomposition and bounded treewidth [18] to arbitrary overlay graphs, not just trees, which may be of independent interest.
1 Introduction
Let G = (V, E) be a connected undirected graph with no multiple edges or loops. The distance between two vertices is the length (number of edges) of a shortest path between them. A (d, c)-coloring is an assignment of colors to the vertices using at most c colors such that no two vertices of distance d or less have the same color. For fixed d and c, the (d, c)-coloring problem is the problem of determining whether a given graph G has a (d, c)-coloring and finding one if so.
The classical coloring problem is the special case d = 1. It is well known that this problem is NP -complete for three or more colors [7]. However, for two colors, the problem is decidable in linear time: a graph is colorable with two colors iff it has no odd cycles, which can be determined in linear time by breadth-first search. Thus (1, 2)-colorability is in P , whereas (1, c)-colorability for c ≥ 3 is NP -complete.
The (d, c)-coloring problem is the same as the (1, c)-coloring problem for the dth power of the graph, which is obtained simply by adding an edge between any
∗Computer Science Department, Cornell University, Ithaca, NY 14853-7501, USA. kozen@cs.cornell.edu
†Computer Science Department, Oberlin College, Oberlin, OH 44074-1073, USA. Alexa.Sharp@oberlin.edu
1

two vertices of distance d or less. However, the (d, c)-coloring problem may be

easier in some cases for small values of c relative to d. In [19], the following sharp

boundary between easy and hard cases was established: for fixed d ≥ 2, (d, c)-

coloring is solvable in linear time for c ≤ 3d/2 and NP -complete for c > 3d/2.

The linear time bound in [19] for the case c ≤ 3d/2 is actually only linear in

the size of the graph, but exponential in d. It uses the fact that for c ≤ 3d/2, a

graph is (d, c)-colorable only if it is of bounded treewidth [18]. The algorithm

constructs a tree decomposition and uses known algorithms for coloring graphs

of bounded treewidth. In [19], a treewidth bound of 5d is obtained. Since the

complexity of the algorithm depends so drastically on d, it is desirable to obtain

a bound on treewidth that is as small as possible.

In this paper we give an alternative construction that improves the treewidth

bound from 5d to 2d. However, the main interest is not the bound itself, but

rather the analysis, which reveals a clear picture of the structure of colorable

graphs. Our construction entails a generalization of the notion of tree decom-

position and bounded treewidth [18] to allow arbitrary overlay graphs, not just

trees, which may be of independent interest. We couple this generalized notion

of decomposition with a general construction that obtains such a decomposition

from a certain class of edge partitions. One such partition is the one determined

by the biconnected components of the graph, which gives a tree decomposition,

but there are others. In particular, the partition we use gives a bounded-width

cycle decomposition of G.

Finally, our analysis sheds light on a particular source of NP -hardness in

graph problems, namely the ability to propagate information nonlinearly in the

graph. To understand what we mean by this, recall that typical NP -hardness

proofs in graphs involve the construction of certain “widgets” that can propa-

gate information in the graph in a controlled way. These widgets can be quite

intricate. For example, to show that planar 3-colorability is NP -complete [7],

one can use the crossover widget shown in Fig. 1. This widget has the properties (i) it is planar, (ii) any legal 3-coloring must color the opposite corners the same, and (iii) every 3-coloring of the corners with opposite corners the same extends to a legal 3-coloring of the whole widget. Thus, by replacing edge crossings with the widget, 3-colorability of arbitrary graphs can be reduced to 3-colorability of planar graphs. We can think of the

r r rdr r r rddr r drdr r  dr  Fig. 1

widget in Fig. 1 as propagating coloring information from the

east corner to the west corner and simultaneously from the north corner to the

south corner.

However, to establish NP -hardness, it is not enough just to be able to prop-

agate information in the graph; it must also be possible to duplicate information

so that it can be propagated nonlinearly. Here we are using the term linear in

the same sense as linear logic [8]. In linear logic, proofs may not freely dupli-

cate assumptions and must consume all occurrences of all assumptions. Every

assertion that is produced is consumed exactly once. Thus the proof rules of

linear logic do not allow the nonlinear propagation of information.

A similar phenomenon arises in combinatorial constraint problems. For ex-

2

ample, in the Boolean satisfiability problem, a 3CNF Boolean formula may con-

tain several occurrences of the same variable. Information is propagated by the

constraint that all occurrences of that variable must have the same truth value.

The general 3CNF satisfiability problem is NP -complete, but the problem is

efficiently solvable under the restriction that each variable occur at most twice.

Intuitively, this restriction prevents the nonlinear propagation of information.

Likewise, in the distance-d coloring problem, the restriction to 3d/2 or

fewer colors essentially prevents the nonlinear propagation of information. A

r r r rr r rZrZZr r
Fig. 2

paradigmatic example is the graph illustrated in Fig. 2 with d = 6. This graph is (6, 10)-colorable, and any legal coloring imposes certain constraints on the colors of any node connected to one of the three terminal nodes. In the (6, 10)-coloring problem, this graph can be used as a widget to propagate coloring constraints nonlinearly. Consequently, (6, 10)-coloring is NP -complete [19]. On the other hand, the graph of Fig. 2 is not (6, 9)-colorable,

so it is a (6, 9)-forbidden subgraph in the sense that it cannot

appear as a subgraph of any (6, 9)-colorable graph. This severely restricts the

form of (6, 9)-colorable graphs to the extent that they are efficiently recognizable

and efficiently colorable.

This paper is organized as follows. In Section 2, we introduce a generalization

of the notion of tree decomposition [18]. Also in that section, we indicate how

such decompositions can be obtained from a certain class of edge partitions,

of which biconnected components are a special case. In Section 3, we show

that for c ≤ 3d/2, (d, c)-colorable graphs have a tree decomposition of width

at most 2d, and we can find such a decomposition efficiently. In one case, this

involves finding a cycle decomposition of width at most d and stringing the two

strands of the cycle together. We conclude in Section 4 with some observations

regarding the homology of colorable graphs.

2 Decomposition
In this section we introduce a generalization of the notion of tree decomposition [18]. In a tree decomposition, the overlay graph is a tree. In our generalization, the overlay graph may be any graph.
2.1 Definition of Decomposition
Let i, j, k be vertices of an undirected graph G = (V, E). The set [i, k ] is the set of all vertices lying on all shortest paths from i to k, inclusive, in G. The set [i, k ] is called an interval. We say that j is between i and k if j ∈ [i, k ]. A set A of vertices is convex if [i, k ] ⊆ A whenever i, k ∈ A. Some basic properties of intervals and convexity in graphs are developed in [14, 15, 16].
Definition 2.1 A decomposition of G is a triple (T, F, X) consisting of an undirected overlay graph (T, F ) and a map X : T → 2V associating a subset Xi ⊆ V with each i ∈ T satisfying the following properties.

3

(i) The Xi cover V ; that is, V = i∈T Xi. (ii) For all edges (s, t) ∈ E, there exists i ∈ T such that s, t ∈ Xi. (iii) If j is between i and k in (T, F ), then Xi ∩ Xk ⊆ Xj.

Equivalent to (iii) is the property:

(iv) For any vertex u, the set {i | u ∈ Xi} is convex. The width of (T, F, X) is maxi |Xi|.

2

A tree decomposition is just a decomposition in which the overlay graph is an undirected tree. In this case, the intervals are just unique simple paths between pairs of vertices and the convex sets are subtrees. We will also consider cycle decompositions and line decompositions in which the overlay graphs are undirected cycles and paths, respectively.

2.2 Decompositions from Edge Partitions
Decompositions can be obtained from certain edge partitions. Let P ⊆ 2E be an edge partition of G = (V, E); that is, a collection of pairwise disjoint nonempty sets of edges whose union is E. For A ∈ P , let V (A) ⊆ V be the set of endpoints of edges in A. Suppose P satisfies the following additional property:
Condition 2.2 If A, B ∈ P and A = B, then |V (A) ∩ V (B)| ≤ 1.
Thus no two partition elements share more than one vertex. If P satisfies this condition, then we call any vertex common to two or more partition elements a local articulation point.
Such partitions give rise to decompositions of G as follows:
Lemma 2.3 Let P be an edge partition of G satisfying Condition 2.2. Let
T = P ∪ {u | V (A) ∩ V (B) = {u} for some A, B ∈ P } F = {(u, A) | u ∈ V (A)} XA = V (A) Xu = {u}.
The structure (T, F, X) is a decomposition of G.
Proof. Properties (i) and (ii) of Definition 2.1 follow from the fact that G is connected and P is a partition of the edges. For property (iii), Xu and Xv cannot intersect for u = v. If Xu and XA intersect, then (u, A) ∈ F , and there is no other vertex of (T, F ) between u and A, therefore (iii) holds vacuously. Finally, if XA and XB intersect, A = B, then by Condition 2.2, XA ∩ XB = {u} for some vertex u, thus [ A, B ] = {A, u, B}, and XA ∩ XB = {u} = Xu. 2

4

A special case of such a decomposition is given by the biconnected components of G and their articulation points [10]. Recall that the biconnected components are the equivalence classes of edges with respect to the equivalence relation defined by: e ∼ e if e and e lie on a common simple cycle. In this case, the decomposition provided by Lemma 2.3 is a tree decomposition of G, and the width is the maximum size of a biconnected component. In this decomposition, the sets XA for A ∈ P are the biconnected components of G and the sets Xu correspond to the articulation points. We will see a generalization of this construction in Section 3.2.
3 An Algorithm
Let c, d ≥ 2 be fixed constants, c ≤ 3d/2. Henceforth, colorable means (d, c)colorable. Let G = (V, E) be a connected undirected graph. Let d(·, ·) be the shortest-path distance function in G.
In this section we describe an algorithm to either construct a constant-width tree, line, or cycle decomposition of G, which can then be used to give a tree decomposition of G of width at most 2d, or declare that G is not colorable. This algorithm can be used in conjunction with known algorithms for coloring graphs of bounded treewidth [12, 17, 3] to either give a coloring of G or declare that no such coloring exists. The algorithm is linear in the size of G for fixed d.
The algorithm proceeds in several steps, which we treat in the indicated subsections.
§3.1 We first partition the graph into biconnected components. We show that there is at most one large component G , otherwise G is not colorable. If there are no large components, we are done. Otherwise, the large component contains a simple cycle T of length at least 2d + 2, which can be found in linear time. The cycle T is called the trunk.
§3.2 We construct a cycle decomposition of G by defining an edge partition satisfying Condition 2.2.
§3.3 Adding the biconnected components removed in §3.1 back in, we show that we obtain a cycle decomposition of width at most c − d/2.
§3.4 Finally, we show how to obtain a line decomposition of width 2w from a cycle decomposition of width w by collapsing the two strands of the cycle.
Any one of these steps may fail if G is not colorable, but this will occur in a recognizable way.
3.1 Biconnected Components
We first find the biconnected components of G. This can be done in linear time [10]. As observed, the biconnected components and their articulation points provide a tree decomposition of G. A biconnected component is small if its diameter is at most d/2, otherwise it is large.
5

Lemma 3.1 If G is colorable, then there is at most one large component.

Proof. If there were two large components, then each would have a cycle of

length at least d. Since the graph is connected, the two large components would

be connected by an isthmus, and one could construct a forbidden subgraph

similar to the one shown in Fig. 2.

2

A large component G must be biconnected and its diameter must be at least d/2 + 1. If 3d/4 < diam G ≤ d, then G (hence G) is not colorable, since there would be a simple cycle of length greater than 3d/2 in a set of diameter d. So either diam G ≤ 3d/4 or diam G > d. If the former, or if there is no large component at all, then each biconnected component is of size at most c, otherwise the graph is not colorable. In this case we have a tree decomposition of width at most c ≤ 3d/2 consisting of the biconnected components, and we are done.
So assume diam G ≥ d + 1. There must exist nodes a, b such that d(a, b) ≥ d + 1, and since G is biconnected, there is a simple cycle T of length at least 2d + 2 containing a and b. We will call the cycle T the trunk. The nodes a, b and the trunk can be found in linear time by depth-first or breadth-first search.

3.2 A Cycle Decomposition

In this section we assume that we have identified a biconnected component G

of diameter at least d + 1. This implies the existence of a simple cycle T in G

of length at least 2d + 2 and two nodes a and b on T of distance at least d + 1.

We will show how to find a cycle decomposition of G of small width, provided

G is colorable. The picture to keep in mind is Fig. 3.

First we prove a lemma that will allow us to construct a r r r r suitable edge partition consisting of the equivalence classes
of a certain equivalence relation ∼d . This partition is very r r much like biconnected components, except that we impose

r

r

r

r

a bound of d on the length of cycles. The following technical lemma is needed for transitivity.

Fig. 3

Lemma 3.2 If G is colorable, then G has no simple cycle of length k for any d + 1 ≤ k ≤ 2d + 1.

Proof. Suppose for a contradiction that there were a simple cycle K of length k with d + 1 ≤ k ≤ 2d + 1. Then diam K = k/2 ≤ d, so by colorability we must have k ≤ c ≤ 3d/2.
The cycles T and K must have a node in common; if not, then since the graph is connected, T and K would be connected by an isthmus, and we could construct a forbidden subgraph like the one shown in Fig. 2.
Since k ≤ 3d/2, there must exist at least |T |−k ≥ 2d+2− 3d/2 = d/2 +2 nodes in T \K. Let x be an arbitrary node in T \K. Let d(x, K) denote the distance from x to the closest element of K. Since T and K share at least one node, x is contained in a maximal segment P of T disjoint from K. The

6

segment P may have no more than d/2 −1 nodes, otherwise we could construct a forbidden subgraph like the one shown in Fig. 2 consisting of nodes from P and nodes from K. Therefore

d(x, K) ≤ ( d/2 − 1)/2 .

(1)

We claim now that

d(a, K) > ( 3d/2 − k)/2 ≥ 0.

(2)

If not, then

d(a, b) ≤ d(a, K) + k/2 + d(K, b) ≤ 3d/2 /2 − k/2 + k/2 + ( d/2 − 1)/2 ≤ 3d/2 /2 − k/2 + k/2 + d/2 /2 = 3d/2 /2 + d/2 /2 = d/2 + d/2 /2 + d/2 /2 ≤ d/2 + d/2 /2 + d/2 /2 = d/2 + d/2 = d,

contradicting the assumption that d(a, b) ≥ d + 1. By symmetry, (2) also gives a lower bound on d(b, K).
Since every node x ∈ T is of distance at most ( d/2 − 1)/2 from K, and since every pair of nodes on K are of distance at most k/2 ≤ 3d/2 /2 , the distance between any element of T and any element of K is bounded by

3d/2 /2 + ( d/2 − 1)/2 ≤ 3d/2 /2 + ≤ 3d/4 + d/4 = d.

d/2 /2

(3)

By (2), a ∈ K. Let Q be the maximal segment of T containing a and disjoint from K. By (3), diam (Q ∪ K) ≤ d. But Q contains at least 2d(a, K) − 1 elements of T \K, thus

|Q ∪ K| ≥ 2d(a, K) − 1 + k ≥ 2 ( ( 3d/2 − k)/2 + 1) − 1 + k = 2 ( 3d/2 − k)/2 + 1 + k ≥ 2 (( 3d/2 − k)/2) + 1 + k = 3d/2 + 1,

contradicting colorability.

2

For edges e, e in G , define e ∼d e if e and e lie on a simple cycle of length at most d. This definition is identical to the definition of the edge partition for biconnected components except for the length restriction. In the presence of the length restriction, the only difficulty would be transitivity, but this is taken care of by Lemma 3.2.

7

Lemma 3.3 If G is colorable, then the relation ∼d is an equivalence relation.

Proof. Reflexivity e ∼d e follows from the fact that the edge e and its two

endpoints constitute a simple cycle. The relation is symmetric, since e and e

can be interchanged in the definition of ∼d .

For transitivity, suppose (u, v) ∼d (u , v ) and (u , v ) ∼d (u , v ). Let C and

C be two simple cycles of length at most d such that (u, v) and (u , v ) occur on

C and (u , v ) and (u , v ) occur on C . Assume u, u , v , v occur in that order

around C. Let x be the first vertex on the segment of C from u to u that also

lies in C ; x must exist, since u ∈ C . Let y be the first vertex on the segment

of C from v to v that also lies in C ; y must exist, since v ∈ C . Also, x = y,

since C is simple. Let P be the segment of C between x and y containing (u, v)

and let P be the segment of C between x and y containing (u , v ). Then

P and P intersect only in x and y, and together they form a simple cycle K

containing (u, v) and (u , v ). The length of K is at most |C|+|C |−2 ≤ 2d−2,

so by Lemma 3.2, its length is at most d, therefore (u, v) ∼d (u , v ).

2

Lemma 3.4 If G is colorable, then no two ∼d -equivalence classes have more than one node in common.
Proof. If u and v were both nodes of distinct ∼d -classes X and Y , then u and v would be of distance at most d/2 in X and at most d/2 in Y . Combining shortest paths in X and Y between u and v would yield a simple cycle of length at most d with edges from both X and Y , thus X = Y . This is a contradiction.
2

Lemmas 3.3 and 3.4 allow us to apply the theory of Section 2. Condition 2.2 follows from Lemma 3.4. Thus the ∼d -equivalence classes give a decomposition of G of width at most c. Later, in Section 3.3, we will improve the width bound.
To show that the decomposition is a cycle decomposition, we need to show how to identify a local articulation point on T . For s, t ∈ T , let (s, t ) denote the open interval [s, t ]\{s, t}. A chord is a path between two nodes of T none of whose intermediate nodes lie on T . We use the notation s, t to represent a chord with endpoints s, t ∈ T . A node u ∈ T is subtended by a chord s, t if u lies strictly between s and t on a shortest path between s and t in T ; that is, if s = u = t and u ∈ [s, t ]. Recall that [s, t ] is the set of all nodes on all shortest paths between s and t in T . There is only one such path unless T is of even length and s and t are diametrically opposed. The chord s, t subtends all the nodes in (s, t ).

Lemma 3.5 If G is colorable, then there exists a local articulation point on T . No local articulation point is subtended by a chord.

Proof. If a node x on T is subtended by a chord, then the two edges on T adjacent to x are ∼d -equivalent, because the length of the chord and the length

8

of the interval of T subtended are at most d/2, otherwise we could construct

a forbidden subgraph like the one shown in Fig. 2. Thus if every node of T is

subtended by a chord, then by transitivity, all edges of T are ∼d -equivalent. But

this cannot be, because no two nodes of distance greater than d/2 on the same

segment of T between a and b can both be in V (A) for some ∼d -class A, because

the diameter of A is at most d/2, and this would short-circuit the distance from

a to b.

2

In fact, by the same argument, the trunk contains at least four local articulation points, thus contains edges from at least four ∼d -classes. Starting from a and moving around the trunk, there must be a local articulation point x within distance d/2 of a, and there must be a second local articulation point y within distance d/2 of x, both of which must be encountered before reaching b. There must be at least two other local articulation points on the other path on T from a to b.

Lemma 3.6 If G is colorable, then G consists of a cycle of biconnected subgraphs, each of diameter at most d/2. Each biconnected subgraph is connected to its two neighbors on the cycle by a local articulation point. We can find the decomposition in linear time.

Proof. The existence is clear from Lemma 3.5. To find the decomposition,

first find a local articulation point s. This can be done in linear time, since every

set of size d/2 must contain a point of T , and there is a local articulation

point no more than d/2 from any node of T . A local articulation point is

recognizable by breadth-first search from s down to a depth of d/2, since it is

not subtended by a chord. We break the graph at s, forming two copies of s,

then find the biconnected components of the resulting graph, which gives the

desired decomposition.

2

3.3 Bounding Cycle Width
Let C be the set of small biconnected components of G that we removed in Section 3.1, and let P be the set of partition elements of G constructed in Section 3.2. In this section we show that, even in the presence of the components C, we can obtain a cycle decomposition of width at most c − d/2.
Let N = V \T the set of non-trunk nodes of G. Except for articulation points, N contains all nodes of V (A) for any small biconnected component A of G.
Let I be an interval in T of length exactly d/2 , which contains exactly d/2 + 1 nodes. Note that T extends at least a distance d/2 on both sides of I. If U ⊆ V , a U -path is a path all of whose intermediate (non-endpoint) nodes are in U . Let B be the set of nodes in N connected to a node in I via an N -path.
If the interval I contains two local articulation points bounding an element of P , then B ∪ I contains that component of P and all small biconnected components of G connected to it via an N -path. Moreover, every small biconnected

9

component of G is so connected to some component of P , and every component of P is so bounded by some I. We wish to show
Lemma 3.7 If G is (d, c)-colorable, then |B ∪ I| ≤ c − d/2.

This will follow from a sequences of lemmas. First we show how to simplify the graph without loss of generality. Delete any edge between a node in N and a node in T \I; every node in B is still connected to I via an N -path, so the definition of B after deleting these edges would still give the same set. Moreover, the graph is still (d, c)-colorable, since deleting edges cannot make it less colorable. Find a spanning tree of the remaining graph containing all edges of I. One edge of T was removed, but add it back in. The resulting graph is still colorable, and all nodes of B are still connected to I via an N -path. Delete all nodes not connected to I, and redefine G to be the resulting graph.
Our simplifications ensure that the graph G consists of the trunk T with a disjoint set of trees branching out from nodes of I. Let Bu be the tree of nodes in B connected to u ∈ I by an N -path. The sets Bu are disjoint and span B. For every node x ∈ B, there is a unique u ∈ I such that x ∈ Bu, and for u = v, Bu and Bv are connected only through u and v.

Lemma 3.8 Let u ∈ I. Then d(x, u) ≤ d/2 − 1 for all x ∈ Bu.

Proof. If not, then there exists x ∈ Bu with d(x, u) = d/2 . The set of

elements on a shortest path in Bu from x to u along with an interval of d + 1

elements of T of which u is the median element form a set of size 3d/2 + 1

and diameter d, contradicting colorability.

2

Lemma 3.9 diam (B ∪ I) ≤ d − 1.

Proof. If diam (B ∪ I) ≥ d, then there exist x, y ∈ B ∪ I such that d(x, y) = d. Let u, v ∈ I such that x ∈ Bu ∪ {u} and y ∈ Bv ∪ {v}. By Lemma 3.8, u = v. Assume without loss of generality that u is to the left of v. Let A consist
of all nodes on a shortest path from x to y (which includes a shortest Bu-path from x to u, followed by a shortest T -path from u to v, followed by a shortest
Bv-path from v to y) along with d(x, u) nodes of T immediately to the left of u and d(y, v) nodes of T immediately to the right of v. Then diam A = d and

|A| = 2d(x, u) + 2d(y, v) + d(u, v) + 1 = 2(d(x, u) + d(u, v) + d(v, y)) − d(u, v) + 1 = 2d(x, y) − d(u, v) + 1 ≥ 2d − d/2 + 1 = 3d/2 + 1,

contradicting colorability.

2

Lemma 3.10 Let z ∈ I be chosen so as to minimize the maximum distance to any other node in B ∪ I. Then d(z, x) ≤ d/2 for all x ∈ B ∪ I.

10

Proof. Let x ∈ B ∪ I maximizing d(z, x). If x ∈ Bz, then we are done by Lemma 3.8. Otherwise, assume without loss of generality that x ∈ Bu for some u to the left of z (the argument is symmetric if u is to the right of z). Let y be
such that d(z, y) is maximum over all elements of all Bv for v = z or v to the right of z. Then

d(x, y) = d(x, z) + d(z, y),

(4)

since the shortest path from x to y goes through z, and

d(x, z) ≤ d(z, y) + 1

(5)

by choice of z: if d(x, z) ≥ d(z, y) + 2, then the node immediately to the left of z would have been a better choice. Using (4), (5), and Lemma 3.9,

d − 1 ≥ d(x, y) = d(x, z) + d(z, y) ≥ 2d(x, z) − 1,

therefore d(x, z) ≤ d/2.

2

Lemma 3.11 |B| ≤ c − d − 1.

Proof. Let D consist of B along with an interval of d + 1 elements of T with

the z of Lemma 3.10 as median element. By Lemma 3.10, diam D = d, thus

|D| ≤ c by colorability, therefore |B| = |D| − (d + 1) ≤ c − d − 1.

2

Lemma 3.7 now follows, since

|B ∪ I| = |B| + |I| ≤ c − d − 1 + d/2 + 1 = c − d/2.

3.4 Converting Cycles to Lines
We have shown that G has a cycle decomposition of width at most c − d/2. Our main result will follow immediately from the following lemma.
Lemma 3.12 If G has a cycle decomposition of width w, then G has a line decomposition of width at most 2w.
Proof. Intuitively, grasp the cycle by diametrically opposed nodes and pull, creating a line with two strands.
Formally, let (T, F, X) be a cycle decomposition of G = (V, E) of width w. Suppose (T, F ) is a cycle of length m + 1 with the vertices of T named 0, 1, 2, . . . , m in order around the cycle. Consider the line (T , F , X ) with
T = {0, 1, 2, . . . , m/2 }, F = {(i, i + 1) | 0 ≤ i ≤ m/2 − 1}, Xi = Xi ∪ Xm−i.
We wish to show that this is a line decomposition of G of width at most 2w. Properties (i) and (ii) of line decompositions hold trivially, and it is clearly of width at most 2w, thus it remains to show property (iii).

11

Suppose 0 ≤ i < j < k ≤ m/2 . We wish to show Xi ∩ Xk ⊆ Xj, or (Xi ∪ Xm−i) ∩ (Xk ∪ Xm−k) ⊆ Xj ∪ Xm−j ,

which by distributivity reduces to the following four inclusions:

Xi ∩ Xk ⊆ Xj ∪ Xm−j Xi ∩ Xm−k ⊆ Xj ∪ Xm−j Xm−i ∩ Xk ⊆ Xj ∪ Xm−j Xm−i ∩ Xm−k ⊆ Xj ∪ Xm−j .

(6) (7) (8) (9)

These inclusions hold by virtue of the fact that (T, F, X) is a cycle decomposition. Properties (6) and (9) are immediate, since j ∈ [i, k ], and by symmetry m − j ∈ [ m − i, m − k ], therefore Xi ∩ Xk ⊆ Xj and Xm−i ∩ Xm−k ⊆ Xm−j.
For (7) and (8), there are two cases, depending on whether

(m − k) − i mod m + 1 ≤ (m + 1)/2 or i − (m − k) mod m + 1 ≤ (m + 1)/2 .

In the former case, j ∈ [i, k ] and k ∈ [i, m − k ], therefore j ∈ [i, m − k ], and by symmetry, m − j ∈ [ m − i, k ]. These imply that Xi ∩ Xm−k ⊆ Xj and Xm−i ∩ Xk ⊆ Xm−j .
In the latter case, we have k − (m − i) mod m + 1 ≤ (m + 1)/2 . Then j ∈ [i, k ] and i ∈ [m − i, k ], therefore j ∈ [m − i, k ], and by symmetry, m − j ∈ [ i, m − k ]. These imply that Xm−i ∩ Xk ⊆ Xj and Xi ∩ Xm−k ⊆ Xm−j. 2

4 Homology of Colorable Graphs
Colorability has deeper implications regarding the cycle structure of the graph that are best expressed in terms of homology. The main observation is Theorem 4.2 below, which says that modulo short simple cycles, there is at most one long simple cycle in the graph.
Let G = (V, E) be a connected undirected graph. Let E be the set of directed edges of G, consisting of two directed edges uv and vu for each undirected edge with endpoints u, v of G. Let ∆ be the set of oriented simple cycles. We write u1u2 · · · un for the oriented cycle that goes through u1, u2, . . . , un, u1 in that order. Call an element of ∆ short if it is of length at most 2d + 1, otherwise long. Let ∆d be the set of short oriented simple cycles. Let H0, H1, and H2 be the free abelian groups on generators V , E, and ∆, respectively. Let H2d be the subgroup of H2 generated by ∆d.
The free abelian group H on a finite set of generators X can be regarded as the set of formal sums e∈X kee, where the ke ∈ Z are integer coefficients. This also forms a Z-module of dimension |X| with standard basis X. We have a natural inner product defined by e • e = 1 if e = e and 0 if e = e for basis elements e, e ∈ X, extended uniquely to H2 → Z by bilinearity. For a basis element e ∈ X, the projection x → e • x gives the coefficient of e in the

12

expression x. We apply this construction in H2, H1 and H0 with standard bases ∆, E, and V , respectively.
For an object α in ∆ or E, we denote by α the object with the opposite orientation. For example, if α is the oriented simple cycle uvw , then α = wvu , and if e is the directed edge uv, then e = vu. The maps : ∆ → ∆ and : E → E extend by linearity to group homomorphisms : H2 → H2 and
: H1 → H1, respectively. Let ∂1 : H2 → H1 and ∂0 : H1 → H0 be the boundary homomorphisms
defined by: for an oriented simple cycle α, ∂1(α) is the sum of the directed edges in α, and for a directed edge uv, ∂0(uv) = v − u. For example, if α is the oriented simple cycle uvw , then ∂1(α) = uv + vw + wu.
If e is a directed or undirected edge with endpoints u, v, let te ∈ ∆ be the unique cycle uv of length 2 consisting of the two directed edges uv and vu. For e ∈ E, ∂1(te) = e + e and te = te. Let H22 be the subgroup of H2 generated by the te.
The cycle group C ⊆ H1 is the kernel of ∂0, which is the same as the image of H2 under ∂1 (Lemma 4.1(i)). Let Cd be the image of H2d under ∂1. The group Cd is the subgroup of the cycle group generated by (the directed edges of) the short oriented simple cycles.
Let Pi be the positive orthant of Hi, 0 ≤ i ≤ 2. This is the set of expressions with only nonnegative coefficients. The set Pi induces a partial order ≤ on Hi defined by: α ≤ β iff β − α ∈ Pi. An element is called positive if it is contained in Pi.
Lemma 4.1
(i) ∂1(H2) = C.
(ii) ∂1(P2) = P1 ∩ C.
Proof. For the forward inclusion of (i), a standard argument shows the image ∂1(H2) is contained in C = ker ∂0; that is, ∂0 ◦ ∂1 = 0. For example, if α = uvw , then
∂0(∂1(α)) = ∂0(uv + vw + wu) = (v − u) + (w − v) + (u − w) = 0.
The forward inclusion of (ii) follows from the observation that the image of a positive element under ∂1 is positive in H1.
For the reverse inclusion, we prove (ii) first. This argument is similar to the proof of Euler’s theorem that a cycle in an undirected graph can be written as a union of simple cycles. If x ∈ P1 and v ∈ V , define the indegree of v in x to be the sum of the coefficients in x of all edges entering v, and define the outdegree of v in x to be the sum of the coefficients in x of all edges exiting v. Observe that for positive x, membership in ker ∂0 is equivalent to the condition that the indegree of every vertex is equal to its outdegree; equivalently, v • ∂0(x) = 0 for all v.
Let x ∈ P1 ∩ ker ∂0. Starting at any node of nonzero outdegree, trace a cycle α1, following edges with positive coefficients in x until encountering a
13

node previously seen. It is always possible to continue, since the outdegree of any node equals the indegree. Subtract off the edges of α1; the resulting expression x − ∂1(α1) is still in P1 ∩ ker ∂0. Continue in a similar fashion to get α2, α3, . . . , until the resulting expression is 0. Let α = i αi. Then x = ∂1(α) and α ∈ P2.
For (i), let x ∈ ker ∂0. Let γ ∈ P2 be a positive sum of length-2 cycles te with coefficients just large enough that x+∂1(γ) ∈ P1. Then x+∂1(γ) ∈ P1 ∩ ker ∂0. By (ii), there exists α ∈ P2 such that ∂1(α) = x + ∂1(γ). Then ∂1(α − γ) = x.
2
For example, the element uv + vw − uw ∈ ker ∂0 is ∂1( uvw − tuw).
Theorem 4.2 Suppose G is (d, 3d/2)-colorable, d ≥ 2. Then either
(i) all simple cycles of G are short, in which case Cd = C and the quotient group C/Cd is trivial; or
(ii) G contains a long simple cycle, in which case the quotient group C/Cd is isomorphic to Z.
Proof. Case (i) is immediate from Lemma 4.1(i). If all simple cycles are short, then H2 = H2d, in which case C = Cd.
For case (ii), assume that G contains an oriented simple cycle T of length at least 2d + 2. By Lemma 3.2, G has no simple cycle whose length lies between d + 1 and 2d + 1, inclusive. In this case Cd is generated by (edges of) simple cycles of length at most d.
We first show that ∂1(T ) is not in Cd, which implies that Cd = C, thus the quotient C/Cd is nontrivial. By general considerations, we know that it is a Z-module of some finite dimension. We will show later that the dimension is 1.
Call an element of H2 reduced if it is an expression of the form β + γ, where
(i) β ∈ P2;
(ii) β is orthogonal to H22; that is, te • β = 0 for all e;
(iii) γ ∈ H22;
(iv) it is not the case that ∂1(te) ≤ ∂1(β) for any edge e.
Intuitively, conditions (i)–(iv) say, respectively, that β is positive, β is a sum of cycles of length 3 or greater, γ is a weighted sum of cycles of length 2, and no two cycles of β contain a complementary pair of edges e, e.
We now claim that for every element of α ∈ H2, there is a reduced expression β + γ ∈ H2 such that ∂1(α) = ∂1(β + γ). Moreover, if α ∈ H2d, then we can ensure that β ∈ H2d; thus the reduction process does not introduce any long cycles.
14

First, express α as a sum β1 + γ1, where β1 is a weighted sum of cycles of length at least 3 and γ1 is a weighted sum of cycles of length 2. Then β and γ satisfy (ii) and (iii). To obtain (i), we observe that

∂1(α + α) = ∂1( (e • α)te);
e
intuitively, all the edges in α + α occur in complementary pairs. Thus

∂1(−α) = ∂1(α − (e • α)te).
e

If β1 = β1+ − β1− with β1+, β1− ∈ P2, let

β2

=

β1+

+

β

− 1

γ2 = γ1 − (e • β1−)te.
e

Then ∂1(α) = ∂1(β2 + γ2) and β2 + γ2 satisfies (i)–(iii).
Note that none of the operations so far have introduced any long cycles. Thus if α ∈ H2d then β2 ∈ H2d.
Finally, to get (iv), suppose ∂1(te) ≤ ∂1(β2). Since te • β2 = 0, we must
have θ, θ ∈ ∆ and e ∈ E such that θ + θ ≤ β2 and ∂1(te) ≤ ∂1(θ + θ ). We have ∂1(θ + θ − te) ∈ P1 ∩ C, so by Lemma 4.1(ii) there exists η ∈ P2 such that ∂1(η) = ∂1(θ + θ − te). Write η as η + η , where η is orthogonal to H22 and η ∈ H22, and let

β3 = β2 − θ − θ + η

γ3 = γ2 + η + te.

Then ∂1(α) = ∂1(β3 + γ3) and β3 + γ3 still satisfies (i)–(iii). Moreover, β3 ∈ H2d if β2 ∈ H2d. To see this, observe that the inner product
with e e gives the sum of the coefficients, which for a cycle gives the length of the cycle. If η = i ηi, where each ηi ∈ ∆, then because θ, θ ∈ ∆d, we have

(( e) • ∂1(ηi)) = ( e) • ∂1(η)

ie

e

= ( e) • ∂1(θ + θ − te)
e

= ( e) • ∂1(θ + θ ) − ( e) • ∂1(te)
ee
≤ 2d − 2,

therefore each ηi in the sum η is of length at most 2d − 2. By Lemma 3.2, it is of length at most d.
The previous step can be repeated only finitely many times before (iv) be-
comes satisfied, because each time the inner product of the current βi with e e decreases by two. We have shown that every α is equivalent modulo ∂1 to a reduced β + γ. Moreover, if α ∈ H2d, then β ∈ H2d.

15

Now we argue that if α ∈ ∆ and ∂1(α) ∈ Cd, then α ∈ ∆d. This implies that ∂1(T ) ∈ Cd, since T ∈ ∆d.
Suppose α ∈ ∆ and ∂1(α) ∈ Cd. If α is of length 2, there is nothing to prove, so assume α is of length at least 3. There is a reduced form expression β + γ such that ∂1(α) = ∂1(β + γ), β ∈ H2d, and γ ∈ H22. For any edge e ∈ E,
(e − e) • ∂1(α − β) = (e − e) • ∂1(γ) = 0,
since γ is a weighted sum of cycles of length 2; therefore
e • ∂1(α) − e • ∂1(α) = e • ∂1(β) − e • ∂1(β).
Because α is a simple cycle of length at least 3, each of e • ∂1(α) and e • ∂1(α) is either 1 or 0, and not both are 1. Also, since β satisfies (iv) of reduced expressions, one of e • ∂1(β) or e • ∂1(β) must be 0. It follows by an easy case analysis that we must have e • ∂1(α) = e • ∂1(β) in all cases. As e was arbitrary, ∂1(α) = ∂1(β). As α is a simple cycle and β is a positive sum of simple cycles, we must have α = β.
Now we argue that there is only one long simple cycle modulo short simple cycles. Let T and T be two oriented long simple cycles. Let a and b be points on T of maximum distance from each other. Let p and q be local articulation points on T such that p is of distance at most d/2 from a, moving in the forward direction on T , and q is of distance at most d/2 from b, also moving in the forward direction. Then p and q are at least distance d + 1 − d/2 = d/2 + 1 apart on T . Since local articulation points are not subtended by chords, removal of p and q disconnects the graph. Moreover, both T and T must traverse p and q, otherwise we could construct a forbidden subgraph like the one illustrated in Fig. 2. Each of T and T traverse p and q exactly once, since they are simple, and we can assume without loss of generality that they are oriented so as to traverse them in opposite directions.
Consider ∂1(T +T ) ∈ C. We will show that this expression vanishes modulo Cd. Every edge e of T is contained in a maximal segment of T all of whose intermediate nodes do not lie on T . This segment constitutes a chord of T consisting of edges of T . The endpoints of the chord are distinct and lie on both T and T . The length of the chord is at least 1 and at most d/2, otherwise we could construct a forbidden subgraph. The length of the segment of T subtended by the chord is at least 1 and at most d/2 for the same reason. Thus these two undirected segments together form a short simple cycle, which we orient in the opposite direction from T ; that is, the cycle contains the edge e for every edge e on the chord. The segment of the short cycle coinciding with T is oriented in either the same direction as T or the opposite direction. Let R be the set of short simple cycles obtained in this way.
Now let γ be a maximal sum of cycles of length 2 such that ∂1(γ) ≤ ∂1(T + T + R). We argue that ∂1(T + T + R − γ) = 0. Consider each edge e ∈ E separately. If neither e nor e is an edge of T or T , then e • ∂1(T +T + R−γ) = 0. If e lies on T but neither e nor e lies on T , then there is exactly one
16

element of R containing e and none containing e. Since both e and e appear in ∂1(T + T + R) with coefficient 1, te appears in γ, and

e • ∂1(T + T + R − γ) = e • ∂1(T + R − γ) = 0.

It remains to calculate the coefficient of e and e in ∂1(T + T + R − γ) for

e = uv lying on T . Suppose p, u, v, q occur on T in that order. Let P be the

segment of T between p and u and let Q be the segment of T between v and q.

The segment of T from q to p traverses an odd number of chords subtending

e, including possibly one of e or e itself, and the traversals from Q to P and

from P to Q must alternate, with one more traversal from Q to P . Each of

these chords is responsible for a cycle of R containing either e or e, depending

on whether the chord goes from Q to P or from P to Q, respectively. So the

coefficients of e and e in ∂1( R) are k and k + 1, respectively, for some k ≥ 0. This includes the case in which e or e is an edge of T , except the value of k is

one greater. Adding in the e from T , we have that the coefficients of e and e in

∂1(T + T + R) are both k + 1. Since γ was chosen maximally, te appears in γ with coefficient k +1, therefore the coefficients of e and e in ∂1(T +T + R−γ) are both 0.

Since e was arbitrary, we have ∂1(T + T + R − γ) = 0, so ∂1(T + T ) = ∂1(γ − R) ∈ Cd, therefore ∂1(T ) is equivalent to −∂1(T ) modulo Cd. We have shown that every element of C is equivalent modulo Cd to kT for some

k ∈ Z.

2

Acknowledgements
This work was supported by NSF grant CCF-0635028. Any views and conclusions expressed herein are those of the authors and do not necessarily represent the official policies or endorsements of the National Science Foundation or the United States government.

References
[1] G. Agnarsson, R. Greenlow, and M. Halld´orsson. On powers of chordal graphs and their colorings. Congressus Numerantium, 144:41–65, 2000.
[2] G. Agnarsson and M. Halld´orsson. Coloring powers of planar graphs. SIAM J. Discrete Math., 16(4):651–662, 2003.
[3] Artur Andrzejak. An algorithm for the Tutte polynomials of graphs of bounded treewidth. Discrete Mathematics, 190:39–54, 1998.
[4] S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. J. Algorithms, 12:308–340, 1991.
[5] A. Bertossi, M. Pinotti, and R. Rizzi. Channel assignment on strongly-simplicial graphs. In Proc. 17th Int. Symp. Parallel and Distributed Processing (IPDPS 2003), 2003.

17

[6] B. Courcelle. The monadic second-order logic of graphs i: Recognizable sets of finite graphs. Inf. Comput., 85:12–75, 1990.
[7] M. R. Garey and D. S. Johnson. Computers and Intractibility: A Guide to the Theory of NP -Completeness. W.H. Freeman, 1979.
[8] Jean-Yves Girard. Linear logic. Theor. Comput. Sci., 50(1):1–102, 1987. [9] P. Heggernes and J. A. Telle. Partitioning graphs into generalized dominating
sets. Nordic J. Computing, 5(2):128–143, 1998. [10] John Hopcroft and Robert Tarjan. Algorithm 447: Efficient algorithms for graph
manipulation. Commun. ACM, 16(6):372–378, 1973. [11] Y.-L. Lin and S. Skiena. Algorithms for square roots of graphs. SIAM J. Discrete
Math., 8:99–118, 1995. [12] J. A. Makowsky. Colored Tutte polynomials and Kaufman brackets for graphs
of bounded tree width. In Proc. 12th ACM-SIAM Symp. Discrete Algorithms (SODA’01), pages 487–495. SIAM, 2001. [13] S. T. McCormic. Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem. Math. Programming, 23(2):153–171, 1983. [14] H. M. Mulder. The Interval Function of a Graph. Mathematical Centre Tracts 132. Mathematisch Centrum, 1980. [15] Ladislav Nebesky´. A characterization of the interval function of a connected graph. Czechoslovak Math. J., 44:173–178, 1994. [16] Ladislav Nebesky´. The interval function of a connected graph and a characterization of geodetic graphs. Mathematica Bohemica, 126(1):247–254, 2001. [17] S. D. Noble. Evaluating the Tutte polynomial for graphs of bounded tree-width. Combinatorics, Probability and Computing, 7:307–321, 1998. [18] N. Robertson and P. D. Seymour. Graph minors II: Algorithmic aspects of treewidth. J. Algorithms, 7:309–322, 1986. [19] Alexa Sharp. Distance coloring. Technical Report TR2007-2071, Computing and Information Science, Cornell University, February 2007. [20] X. Zhou, Y. Kanari, and T. Nishizeki. Generalized vertex-coloring of partial k-trees. IEICE Trans. Fundamentals, E83-A:672–678, 2000.
18