Excluding any graph as a minor allows a low tree-width 2-coloring.
This article proves the conjecture of Thomas that, for every graph G, there is an integer k such that every graph with no minor isomorphic to G has a 2-coloring of either its vertices or its edges where each color induces a graph of tree-widlh at most k. Some generalizations are also proved.
Introduction
A vertex partition of a graph G, into n parts, is a set {P 1 , - , P n } of induced
subgraphs of G such that # n
An edge partition of a graph G, into n parts, is a set {Q 1 , - , Q n } of subgraphs
of G such that # n
partition into n parts, can be associated with a coloring (of edges or vertices, as
appropriate) with n colors in the obvious way.
The edge partition {Q 1 , - , Q n } of a graph G is balanced, as witnessed by a
vertex partition {P 1 ,
j. This is a technical condition needed later. In terms of
colorings, with a set of colors C, the edge coloring,
witnessed by a vertex coloring, c for every edge e with endpoints u, v,
it holds that c E
Given a graph G, a T -decomposition of G is a pair (T , X), where T is a graph,
and for each vertex t of T , there is a bag X t # V (G) such that
and the following are satisfied.
(2) For every edge xy of G, there is a t # V (T ) such that {x, y} # X t .
(3) For every x # V (G), the subgraph of T induced by {t # V
connected.
The width of (T , X) is
Date: May 1, 2001.
1991 Mathematics Subject Classification. Primary: 05C15; Secondary: 05C55.
Key words and phrases. tree-width, vertex partitions, edge partitions, small components.
This author's research was partially supported by National Science Foundation under Grant
DMS-9400946.
This author's research was partially supported by the National Security Agency, grant number
MDA904-94-H-2057.
3 This author's research was supported by the O#ce of Naval Research, grant number N00014-
92-J-1965.
4 Research of these authors was partially supported by the Louisiana Education Quality Support
Fund, grant LEQSF(1995-98)-RD-A-08.
If T is a tree, then (T, X) is a tree-decomposition. The tree-width of a graph G,
denoted tw(G), is the smallest integer w such that G has a tree-decomposition of
width w. A graph is a partial k-tree if it has tree-width at most k. Tree-width is
important not only for its theoretical application in the graph minors project, but
also for its algorithmic qualities: many problems which are NP-hard for the class
of all graphs are solvable in linear time for the class of graphs of tree-width at most
k for every fixed k.
Given graphs G and H, G is a minor of H, denoted G #m H, if G can be
obtained from a subgraph of H by contracting edges. If a G is not a minor of
H, then H is a graph with no G-minor. An important result of Robertson and
Seymour [5] (see also [8]) is that if P is a planar graph, then there is an integer k
such that every graph G with no P-minor has tree-width at most k. This is not
true for any non-planar graph, as the n - n planar grid has tree-width n (see [4]).
The authors [2], generalizing a relaxation of a conjecture in [1], showed that, given
any surface, although a graph G embedded on that surface may have arbitrarily
large tree-width, G has both a vertex partition and an edge partition into two
graphs whose tree-width is bounded by a function depending only on the Euler
characteristic of the surface. The set S of all graphs embedded on a surface is an
example of a minor-closed class, that is, if G # S, and H #m G, then H # S.
Thomas [9] conjectured that every minor-closed class of graphs, other than the
class of all graphs, should have this partition property. In other words, Thomas
conjectured, and we prove, the following theorem.
1.1. Theorem. For every graph K, there are integers k
such that every graph with no K-minor has a vertex partition into two
graphs with tree-width at most k V , and an edge partition into two graphs with tree-width
at most kE .
This follows from the following stronger theorem.
1.2. Theorem. For every graph K and integer j # 1, there are integers k
j), such that every graph with no K-minor has a vertex
partition into such that any j parts form a graph with tree-width at
most k V , and an edge partition into j +1 graphs such that any j parts form a graph
with tree-width at most kE .
Also we prove this.
1.3. Theorem. For every graph K and integer j # 1, there are integers
j), such that every graph with no K-minor has a vertex
partition into i V graphs such that any j # j parts form a graph with tree-width at
most and an edge partition into i E graphs such that any j # j parts form
a graph with tree-width at most j # .
The proofs of these theorems are completed in Section 6. These proofs will be
accomplished as follows. First, an important result of Robertson and Seymour,
Theorem 2.1, on the structure of graphs without a particular graph as a minor will
be stated in Section 2. A corollary of Theorem 2.1, namely Corollary 2.2, will be the
structural graph-theoretic result we actually use. This structure has elements both
of surfaces and of tree-width in it. The main structure is a surface-like structure
called an outgrowth. The partitions to be defined will break an outgrowth up into
pieces called layers of bounded height. These partitions and layers are considered
in Section 3. A bound on the tree-width of layers is established in Section 4.
Then Section 5 deals with two other graph constructions mentioned in Section 2,
namely extensions and clique-joins. Finally, as already noted, the main proofs are
completed in Section 6.
To assist in the proofs, some important relationships between tree-width and
graph minors are needed. The proofs of these results follow easily from the definitions
of tree-width, minor, and the following. A clique is a complete subgraph.
Given two graphs G and H, a graph J is a clique-join of G and H if G # H is a
clique, and J is a subgraph of G # H.
1.4. Lemma. (1) If G #m H, then tw(G) # tw(H).
(2) If H is a clique-join of G 1 and G 2 , then tw(H) # max{tw(G 1
(3) If there is a vertex x such that
2. Excluding a Graph
Let P n be the path on vertices (in be the circuit on
vertices (in cyclic
Given a positive integer r, an r-ring with perimeter t 1 , - , t n is a graph R on the
vertex set {t 1 , - , t n } such that there is a family of bags
for
-decomposition of R of width r - 1,
Note that our definition of r-ring di#ers from that in [6] in that we require all
vertices to be on the perimeter. However, if vertices were not required to be on the
perimeter, an easy construction would put them on the perimeter without violating
any condition in this paper.
We introduce a closely related concept. An r-round with perimeter t 1 , - , t n
is a graph R on the vertex set {t 1 , - , t n } such that there is a family of bags
-decomposition of R of width r - 1,
Observe that if
n) is an r-ring with perimeter t 1 , - , t n ,
then X is also an r-round with the same perimeter. Note that width r - 1 means
that
denote the set of strings of letters from an alphabet V . A
supergraph H consists of a vertex set an edge set
an incidence function I (Often we identify e with its vertex string
I H (e).) For comparison, an edge in a hypergraph is (associated with) a set of
vertices, whereas an edge in a supergraph is associated with an ordered list of
vertices (possibly with repetition). An edge
then e is non-degenerate otherwise it is degenerate.
Two strings in V # are cyclically equivalent if one can be obtained from the other
by a sequence of moves that are reversals v 1
Throughout this paper, every edge in a supergraph has size at least two. An edge
in a supergraph H is a 2-edge if it has order two, otherwise it is a superedge. Let
denote the set of all 2-edges and let E 3 (H) denote the set of all superedges.
A supergraph H is embedded on a surface # as follows. Each vertex is a point.
Each 2-edge, e, is the image of a continuous injective map f e : [0, 1] #, where
f e (0) and f e (1) are the endvertices of e. Each superedge, is the image
of a continuous map f # : D # where D # is a closed disk with distinct points,
in cyclic order on the boundary, such that f # . The continuous
mapping f # is injective on D - {t 1 , - , t n }. Thus, if # is non-degenerate, then
the image f # (D # ) is a closed disk, otherwise it is obtained from a closed disk by
identifying certain points on the boundary. There are no intersections between
pointsets of vertices and edges except those mentioned here.
Sometimes we identify the vertices and edges of (super)graph H with their
pointsets on the surface #. The faces of H on # are the connected components of
# -H. A crosscap (respectively, handle) reduction of a surface is performed by replacing
a crosscap (respectively, handle) by a disk. We say surface # is a reduction of
surface #, and we write #, if # is obtained from # by a (possibly empty)
sequence of crosscap and handle reductions. We declare that an embedding of a
supergraph H on # is also an embedding on #, whenever #.
We define crosscap and handle reductions on faces similarly. Thus, without loss
of generality, we may always perform all possible crosscap and handle reductions
on faces. We define two other constructions we may be able to use under certain
circumstances. If a face is a surface punctured k times, (that is, it has k disjoint
boundaries), we cap the face by replacing it with k disks. We span the face by adding
new 2-edges in the face, so the boundaries are joined into one boundary.
Thus, provided we can do face reductions together with cappings or spannings,
we may assume that every face is an open disk.
Throughout this paper, unless otherwise noted, we assume that every graph G,
every supergraph H, and every surface # is connected, and that every face is simply
connected, that is, every face is an open disk.
Given a surface # and a positive integer r, let a (#, r)-outgrowth be a pair (G, H)
where G is a graph, and H is a supergraph embedded on #, where for each superedge
there is an r-ring R # with perimeter t 1# , - , t n# ,
such that G is the graph obtained from H by replacing each superedge # by r-ring
R # , as follows. Starting with vertex disjoint copies of the graphs H|E 2 (H) and
every
Given a surface # and positive integers r, s, let a (#, (r, s))-outgrowth be a triple
(G, H, # 0 ) where G is a graph, H is a supergraph embedded on #, and #
such that G is the graph obtained from H by replacing # 0 by an s-round and by
replacing every other superedge by an r-ring, as described in detail above. Again,
clearly
If (G, H) or (G, H, # 0 ) is an outgrowth, we refer to the graph G as the graph from
the outgrowth. Note that in [6], the graph itself is referred to as the outgrowth.
Note also that our definition of outgrowth di#ers from that in [6] in that we allow
superedges to be degenerate.
If # is a non-empty set of surfaces, then (G, H) is a (#, r)-outgrowth if there is
a # such that (G, H) is a (#, r)-outgrowth. Let K 0 be the empty graph. It
is intended that (K 0 , K 0 ) is a (#, r)-outgrowth for all possible values of # and r.
Thus for any set # of surfaces, (K 0 , K 0 ) is a (#, r)-outgrowth. If # is empty, then
let (K 0 , K 0 ) be the only (#, r)-outgrowth. We repeat all these definitions where r
is replaced by (r, s).
Given an integer k, let G # be a (# k)-vertex extension of G if there is a set S of
at most k vertices of H such that -S. For example, the set of apex graphs
is the set of graphs which are (# 1)-vertex extensions of planar graphs.
The following is a major structural result from [6]. This theorem followed from
an important step in proving the Graph Minors Theorem [7].
2.1. Theorem. (Robertson and Seymour)
Let K be a graph, and let #(K) be the set of all surfaces in which K cannot be
embedded. Then there are numbers r(K), w(K) and d(K) such that every graph
with no K-minor may be constructed by clique-joins, starting from (# w(K))-vertex
extensions of graphs from (#(K), r(K))-outgrowths
no degenerate edges.
It should be mentioned that Theorem 2.1 was proved with a slightly di#erent
understanding of r-rings as noted above. However, it is easy to show that this
theorem remains valid if we additionally require that all vertices of an r-ring are
on the perimeter, as we do in this paper.
We wish to use a modified version of the structural theorem above, by removing
the bound d(K) on the number of superedges (and r-rings), and by removing the
requirement that superedges be non-degenerate.
2.2. Corollary. Let K be a graph, and let #(K) be the set of all surfaces in which K
cannot be embedded. Then there are numbers r(K) and w(K) such that every graph
with no K-minor may be constructed by clique-joins, starting from (# w(K))-vertex
extensions of graphs from (#(K), r(K))-outgrowths.
Note that if K is a planar graph, then #, and a graph with no K-minor
may be constructed by clique-joins, starting from graphs on at most w(K) vertices.
This special case of Theorem 2.1 (or Corollary 2.2) that, for every planar graph P ,
a graph with no P-minor has low tree-width, appears in [5] (see also [8]).
3. Layers
The main step towards proving Theorem 1.2 is finding an edge and a vertex
(j 1)-coloring, of a (#, r)-outgrowth (G, H), such that any j colors form a graph
with bounded tree-width. (The bound would involve #, r and j.) Clearly there will
be no loss of generality in adding new edges to G and H, nor in deleting parallel
2-edges. We will describe two such constructions shortly.
We first examine the boundary of a face, which may be more complicated than
just a circuit. For a face F , let -
F denote its closure and let
its boundary. Let DF be a closed disk, with interior D # F
and boundary #DF . A
continuous injective map from D # F
to F extends uniquely to a continuous map
be the list, in cyclic order, of all points of #DF that
are mapped to vertices. Let v n. The string v 1 - v n is a
vertex-boundary of F . This string is unique up to cyclic equivalence.
The face F has order ||F
non-degenerate otherwise it is degenerate.
For a face F with vertex-boundary v 1 - v n , n # 3, we fill F with a trivial
superedge # F and r-ring R #F by adding a new superedge # embedded
in the natural way. Note that the pointset of F is replaced by the pointset of # F
(minus its vertices) and n new faces of order two incident with # F . The trivial r-
ring R #F has no edges and has bag X for each perimeter vertex t. Similarly,
we may fill a face with a trivial s-round.
For any superedge by adding those 2-edges v i v i+1( mod n)
to G and H which are not already present. They are embedded in the natural way.
Suppose F 0 is a face of supergraph H. We say that H is full (respectively,
is full) if every face (respectively, other than F 0 ) has order two, and is incident with
one 2-edge and one superedge. We fill H (respectively, performing all
possible face fillings (respectively, except on F 0 ) and all possible encyclings.
The set of elements, P (H) of a supergraph H on surface # is the set of all
vertices, edges and faces of H on #.
We define a (symmetric) incidence relation on the elements of H. A vertex v is
incident with edge vertex v is incident with face
F . A face F is incident with an edge e if -
F intersects the pointset of e in
a point other than a vertex. No other incidences a possible, in particular, elements
of the same type cannot be incident.
We define a metric, d : P (H)-P (H) # R on the elements of H. Let d(a,
where m is the least integer such that a consecutive entries
in the sequence p 0 - pm are incident. In particular d(a, 1if and only if a and
b are incident.
Given a connected supergraph H drawn on a surface # and a face F 0 , the
height, h H
of an element x # P (H), relative to F 0 , is given by
every vertex has integer height.
If (G, H) is a (#, r)-outgrowth, F 0 is a face of H and 2h # 0 is an integer,
then (G, H,F 0 ) is a (#, r, h)-layer provided that every vertex and edge of H has
height at most h. Layers are of interest because the vertex and edge partitions
of (#, r)-outgrowths that we will define have components which are, respectively
(#, r, h)-layers for some h to be specified later. We will prove this assertion after
some definitions. (The following section proves that these layers have bounded
tree-width.)
We use a traditional approach to defining a vertex and edge partition of an
outgrowth (G, H) based upon distance from a given face F 0 of the supergraph.
Without loss of generality (H, F 0 ) is full. For each integer h # 0 let V h be the set
of vertices at height h. For integers be the set of edges of G
which have one end at height i and the other at height j. (Note that E
similarly. Observe that the edges in E h-1,h all
have height h - 1, whereas the edges in E h,h may have heights h - 1, h or h
and if e is a 2-edge.
It is convenient to define vertex and edge partitions via colorings. For an integer
l # 2, the set of colors will be Z l , the integers mod l. The canonical vertex l-
coloring assigns color h( mod l) to all vertices in V h . The canonical edge l-coloring
assigns color h( mod l) to all edges in E h-1,h #E h,h . Note that this edge-coloring
is balanced, as witnessed by the given vertex coloring.
We will be interested in subgraphs formed by some 1 # j < l of these colors, and
in bounding the tree-width of (the components of) these subgraphs. Since adjacent
vertices or edges can di#er in height by at most one, it is su#cient to bound the
tree-width of the following two types.
a
a
We wish to express -
G [a,b] as an outgrowth of an appropriate supergraph. This
is done naturally, but we provide details. Suppose, in general, G
subgraph of G where (G, H) is a (#, r)-outgrowth with F 0 a face of H, and r-ring R #
associated with each superedge # E 3 (H). We define an outgrowth (G # , H # ) and
a layer (G # , H # , F #
from either E 2 (H) or some r-ring R # . Also, delete the edges in
from the drawing of H on #. After deleting these edges, this leaves the vertices to
be deleted, Remove each vertex in V - V # from the drawing of
H, from the vertex list of each superedge, from every r-ring perimeter and every
bag. If, after these deletions, the superedge # has size less than two, then delete
it. If, after these deletions, the superedge # has size two, say with incident vertices
u, v, and edge uv is in R # , then replace # with a 2-edge uv, otherwise just delete
it. Otherwise, make the new embedding of disk D # , representing #, a subset of the
old embedding such that it only hits the appropriate remaining vertices. Let F #be
the face of H # that contains the pointset of F 0 . Note that F #need not be simply
connected.
Continue by reducing, capping and filling all faces other than -
F [a,b] . Reduce and
span face -
which is full, by construction.
3.1. Lemma. Suppose (G, H) is a (#, r)-outgrowth, with face F 0 , such that
is full. For integers l # 2,
a full (#, r, j + 1)-layers. Moreover G V
and G E
are subgraphs of G [a,b] .
Proof. These statements are clear except for the bound j + 1on height of
that the edges added by filling faces other than -
all have endpoints in V b (G) and without loss of generality we may assume these
edges were already in G. If a = 0, the result is immediate, so we may suppose
a > 0. Now, considering heights in the original (G, H,F 0 ), the vertices of G [a,b]
have heights ranging from a - 1 to b and the edges of G [a,b] have heights ranging
from a - 1to b + 1. Now all the vertices and edges of G [a,b] that had height
a - 1 in (G, H,F 0 ), are incident with the face F [a,b] in H [a,b] , so their height in
L is zero. Consequently, all other vertices and edges of G E
have height in L
that is a - 1 less than its original height in (G, H,F 0 ). Thus L has height at most
The above bounds on height are best possible.
4. Bounding the tree-width of (#, r, h)-layers
This section establishes a bound on the tree-width of a (#, r, h)-layer in terms
of #, r and h.
h)-layer is a triple (G, H, #(F )) where H has a special superedge
associated other superedge has an associated r-
ring; G is obtained from H by replacing superedges by the s-round and r-rings;
h)-layer, where F is created by the deletion
of #(F ). (Note that F is not a face of H.) The height of #(F ), and its incident
faces, is declared to be - 1. All other vertices and edges have the same height in
For a surface #, let #) denote the Euler characteristic of #.
Let #h# denote h - #h#, the fractional part of h. The following is the main
theorem of this section.
4.1. Theorem. If (G, H, #(F )) is a full (#, (r, s), h)-layer, then G has tree-width
at most
The proof of the theorem will follow some lemmas and definitions. Before stating
these, we prove two easy corollaries, which will be used in the proof of the main
theorem appearing in the next section.
4.2. Corollary. If (G, H,F ) is a full (#, r, h)-layer, then G has tree-width at most
Proof. Fill face F with an s-round with apply Theorem 4.1. #
4.3. Corollary. Let G be a connected graph such that (G, H) is (#, r)-outgrowth,
and let F be a face of H. Then G has a balanced edge and a vertex l-coloring, such
that any j < l colors form a graph with tree-width at most
Proof. This follows from Lemma 3.1, and the preceding discussion, with
The 2-degree of a vertex v in a supergraph H, denoted deg 2 v is the degree of
v in full supergraph is subcubic if every vertex has 2-degree at most
three.
For
#,t denote the bag associated with superedge # and
perimeter vertex t on R # for L.
Note that H being full implies that the edges listed cyclically around any vertex
alternate between 2-edges and superedges.
4.4. Lemma. If there is a counterexample to Theorem 4.1, then there is a counterexample
with H full and subcubic.
Proof. As discussed above, we can suppose the supergraph H is full without loss of
generality. The remainder of the proof is similar to the proof that any graph can
be obtained from a subcubic graph by contraction, although here we must preserve
height and other structure.
Suppose x is a vertex with 2-degree more than three. Let the height of x be j.
Let the cyclic ordering of edges around x be (where each # i is a
superedge and each e i is a 2-edge) such that, without loss of generality, the height
of # 1 is j - 1. Suppose l # {3, - , m- 1}.
We define the height preserving decontraction of x through to
obtain Remove x from H and add two
new vertices x # and x # . Add a new 2-edge e Each edge in # 1 , e 1 - , e l-1 , # l
is declared to be incident with x # . Each edge in # l , e l - declared to
be incident with x # . H # is embedded naturally. For y # {x # , x # } and # incident
with y in H # , the bag X L #
#,x # {y} - {x}. For any other bag Y , with x # Y
associated with # 1 or # l in H we change Y to Y # {x # } - {x} or Y # {x # } - {x}
so as to preserve the required properties for r-rings and s-rounds. This creates a
Note, by the choice of # 1 this operation does not increase height. By finitely many
height preserving decontractions we obtain a
that H # is subcubic and G # is a minor of G. By Lemma 1.4 (1) the result follows.
Sometimes it is useful to rotate the perimeter around an r-ring. The next simple
lemma shows that this may be done by adding a factor of two to its width.
4.5. Lemma. If R is an r-ring with perimeter t 1 , - , t n , then for each i such that
(2r)-ring with perimeter t
Proof. Let R be an r-ring with perimeter t 1 , - , t n by means of bags
be given. For each . Then the
give the result. #
4.6. Lemma. If there is a counterexample to Theorem 4.1, then there is a counterexample
with H full, subcubic with height h < 1.
Proof. Suppose the (#, (r, s), h)-layer,
H is full and subcubic, with the height h as small as possible. Suppose h # 1. We
shall construct a (#, (r, s as follows, to
obtain a contradiction. For
(H) denote the set of edges in E i (H)
which have height h. Since H is full and subcubic, for every superedge # E2(H),
there is a 2-edge
2 (H) such that # and e(#) bound a face. By finitely many
height preserving decontractions we may ensure that these 2-edges form a matching.
Applying Lemma 4.5 we rotate the r-ring R # associated with each # E2(H), to
obtain a 2r-ring R #
with perimeter
Construct H # from H by deleting #(F ), and every # and e(#) for
# E2(H), creating a face F # , and then filling F # with a superedge #(F # ).
We now need to associate with #(F # ) an 1)-round, by specifying all
the bags, so that (G, H #(F # )) has the required properties. For each # E2(H),
with R #
for
of
corresponds naturally to a vertex of #(F ) so we leave the bag unchanged.
It is routine to check that L # has the required properties and the lemma follows.
We now complete the proof of the Theorem 4.1.
Proof. Suppose (G, H, #(F )) is a (#, (r, s), h)-layer which contradicts the theorem.
By the above lemmas we may assume that H is full and subcubic and that h #
Suppose first that h = 0. Then H has a single superedge #(F ). Let H
is a graph on # with a single face F . By Euler's formula, there
is a set C of exactly 2 -#) edges such that is a spanning tree of H 2 .
For each x # V (G) let T x be the set of all vertices v # V (G) such that x is in some
bag associated with v. Clearly H 2 |T x is connected for every x # V (G).
Now each 2-edge is associated with four entries (each with a corresponding bag)
in the vertex-list of the face F . Let Y e and Z e be the two bags at one end of e. For
any x, if e # H 2 |T x , then x # Y e #Z e . Let
G-D.
Now G # is obtained from G by the deletion of at most (2 - #))(2s - 1) vertices
so by Lemma 1.4,
A tree-decomposition of G # of width 3s-2 (that is, with bag size at most 3s-1)
is obtained as follows, using tree T . Arbitrarily choose a root z of T . For each
bag be the union of the bags (with D removed) associated with
x in L together with the predecessor (if any) of x in the rooted tree. The result
The result for similarly after a reduction similar to that in the
proof of Lemma 4.6. We just briefly outline the modifications to the arguments for
this case. We do not need to rotate any r-rings for this construction, although we
may first have to do some decontractions (at no cost to the bounds). We reduce to
the case where, at worst, each vertex is associated with one bag of size s and
two of size s 1. The edges in E2(H) form a matching and so we assume the
tree T contains all of these to obtain the required bound. #
5. Extensions and Clique Sums
In this section we extend the partition results from outgrowths to minor-closed
classes. It will become apparent why the edge partitions of the previous sections
were required to be balanced. This property is very useful in dealing with clique-
joins.
For a set of surfaces #, and integer r # 1, let #,r be the set of all graphs from
(#, r)-outgrowths.
For a set of graphs # and integer w # 0, let #w be the set of all pairs (G, W )
where G is a graph and W # V (G) such that |W | # w and (G -W ) #. We call
the vertices in W the extra vertices of G.
w be the set of graphs G for which there exists W such that (G, W ) #
is the set of all graphs that are (# w)-vertex extensions of
graphs in #.
inductively as follows:
G is a clique-join of G 1 and G 2
on a clique Q with
The only restriction from taking arbitrary clique-joins is that V (Q) # W . Theorem
2.1 and Corollary 2.2 still hold with such a restriction imposed, and so we get
a further corollary.
5.1. Corollary. Let # be a minor closed class of graphs other than the class of all
graphs. Then there is a finite set of surfaces, #, and there are numbers r and w
such that
Proof. Choose graph K #. Let w(K). The result
follows from Corollary 2.2 modified with the above noted restriction on clique-
joins. #
Let C be a set of colors. Let E) be a graph. For an edge coloring
B}. For a vertex
coloring
We say that graph G has a (k B
for all B # C. Make a similar
definition for vertex coloring.
If the edge coloring, witnessed by a vertex coloring,
we may combine these into a balanced full coloring
this has the property that for every edge e with endpoints
u, v, it holds that c(e) # {c(u), c(v)}. We call this condition the endpoint rule. We
say c is a balanced (k B
full coloring, if C|E is a balanced (k B
edge coloring.
5.2. Lemma. Suppose that # is a set of graphs, and w # 0 is an integer. Let C be
a set of colors. Suppose k B
(1) If every graph in # has a (k B
then G has a
(2) If every graph in # has a balanced (k B
then G has a balanced (k B
Proof. (1) Let # be a set of graphs, such that every graph in # has a (k B
vertex coloring. Suppose G #
there exists W such that (G, W ) # w. Thus G-W #
and so has a (k B
coloring. If we extend the coloring from G-W
to G by arbitrarily coloring W , then the result follows, using Lemma 1.4(3).
Now suppose G 1 #+w# and (G 2 , W ) #w and G is a clique-join of G 1 and
G 2 on a clique Q with V (Q) # W . By induction there is a
coloring of G 1 and there is a
coloring of G 2 - W . Note that
the graphs G 1 and G 2 - W are vertex disjoint so we may use these two colorings
to vertex color G 1 # (G 2 -W ). This leaves the vertices in W -V (Q) to be colored,
and we do so arbitrarily.
Observe, for any B # C, that G|V (B) is a clique-join of G
on the clique with vertex set
as required.
(2) Let # be a set of graphs, such that every graph in # has a (k B
coloring. Suppose G #
We wish to find a balanced (k B
we also give a vertex coloring c that witnesses that c E is balanced,
and we combine these into a balanced full coloring . Thus, we will color
both edges and vertices of G such that every edge satisfies the endpoint rule.
If G #+w, then there exists W such that (G, W ) #w. Thus G-W # and
so has a balanced (k B
full coloring. If we extend the coloring from G-W
to G by arbitrarily coloring W , and coloring edges incident with vertices arbitrarily
subject to the endpoint rule, then the result follows, using Lemma 1.4(3).
Now suppose G G is a clique-join of
G 1 and G 2 on a clique Q with V (Q) # W . By induction there is a balanced
full coloring of G 1 and there is a balanced (k B
coloring of G 2 -W . Note that the graphs G 1 and G 2 -W are vertex disjoint so we
may use these two colorings to fully color G 1 # (G 2 -W ). This leaves the vertices
in W - V (Q), and the edges incident with these vertices, and the edges between
to be colored. We color these vertices and edges arbitrarily,
subject to the endpoint rule, except that for any edge e with endpoints
and
For any B # C, there are no edges in G|E(B) between
(Q), by the above choice of coloring for edges between V (Q) and V
Therefore G|E(B) is a clique-join of G 1 |E(B) and G 2 |E(B), on the clique with
6. Proofs of Main Theorems
In this section, we prove the theorems stated in Section 1, as well as some other
theorems. For a finite set of surfaces # let
6.1. Theorem. Let # be a finite set of surfaces, and let r # 1, w # 0 and l # 2
be integers. Then every graph in (#,r has a balanced edge and a vertex
l-coloring, such that any j < l colors form a graph with tree-width at most
Proof. This follows from Corollary 4.3 and Lemma 5.2. #
6.2. Theorem. Let # be a minor closed class of graphs other than the class of all
graphs. Let l # 2 be an integer. Then there exist numbers # and # such that every
graph in # has a balanced edge and a vertex l-coloring, such that any j < l colors
form a graph with tree-width at most #j
Proof. This follows from Corollary 5.1 and Theorem 6.1. #
The proofs of Theorem 1.1 and Theorem 1.2 follow immediately.
Finally we need to prove Theorem 1.3. We first consider partitioning graphs of
bounded tree-width. This topic was examined in [3], but we need a new formulation
here.
A k-tree G is a graph with the following structure. Suppose n > k, let
of v j in G|V j is a k-clique. Observe that the largest clique in G has size k + 1.
(Recall that, a subgraph of a k-tree is a partial k-tree and every (simple) graph
with tree-width at most k is a partial k-tree.)
1} be a set of colors. We define the canonical balanced full
we extend the vertex coloring uniquely, subject to being a proper vertex coloring.
If edge e has endpoint v i and v j with i < j, then we color
6.3. Theorem. Let has tree-width at most k, then G has
a balanced full coloring c : V (G)
and G|E(B) is a |B|-tree for every B # C.
Proof. Without loss of generality G is a k-tree. Let c be the canonical balanced
full coloring. Let E(B). Observe that
is a |B|-clique and for k < then the neighborhood
of v j in G|V j is a (|B| - 1)-clique. So G|V (B) is a (|B| - 1)-tree.
Now G|E(B) is obtained from G|V (B) by attaching each vertex in V -V (B) to
a |B|-clique. So G|E(B) is a |B|-tree. #
For a vertex coloring c, let # c denote the corresponding vertex partition. The
of two vertex colorings c 1 and c 2 is defined by (c
(v)), that is, each vertex gets an ordered pair of colors. For a family
of colorings similarly. Make similar definitions for edge
colorings and partitions. Clearly,
i#I
Also,
The following theorem sounds technical, but it is straightforward and very useful.
For a set C and integer j let # C
6.4. Theorem. The following statement holds for both edge and vertex colorings.
be classes of graphs. Suppose, for all j, that # j is
closed under subgraphs (respectively, induced subgraphs) in the edge (respectively,
coloring case. Let j # 1, l # j, m # j, be integers.
(1) Suppose that every graph in # can be l-colored so that every j colors form
a graph in # .
(2) Suppose that every graph in # can be m-colored so that, for every j # j,
every colors form a graph in # j # .
Then there exists an integer i such that every graph in # can be i-colored so that,
for every j # j, every j # colors form a graph in # j # .
Proof. We prove it in the edge case. (The vertex case is almost identical.) Let G #
and let c : E(G) # C be a coloring satisfying (1), where C is a set of colors of size
l. For each B # C
be a coloring satisfying (2), where CB is
a set of colors of size m. Extend coloring CB to all of E(G) by assigning a single
new color #, say, to each edge in E(G)-E(B), to yield c # B
. Then c # is the desired coloring, and it uses at most i # (m
colors. #
We may now prove Theorem 1.3. In fact it follows from the following stronger
theorem, using Corollary 5.1.
6.5. Theorem. Let # be a finite set of surfaces, and let r # 1, w # 0, and j # 1
be integers. There are integers i V and i E , such that every graph in (#,r
has a vertex partition into i V graphs such that any j # j parts form a graph with
tree-width at most j # - 1, and an edge partition into i E graphs such that any j # j
parts form a graph with tree-width at most j # .
Proof. This follows from Theorem 6.1, Theorem 6.3, and Theorem 6.4. #



--R

Graphs with forbidden subgraphs

Partitioning graphs of bounded tree- width
Graph Minors.
Graph Minors.
Graph Minors XVI.
Graph Minors XX.
Quickly excluding a planar graph
Problem Session of the Third Slovene Conference on Graph Theory
--TR
Graph minors. V. Excluding a planar graph
Quickly excluding a planar graph
Surfaces, tree-width, clique-minors, and partitions
Graph minors. XVI. excluding a non-planar graph

--CTR
Jaroslav Neetil , Patrice Ossona de Mendez, Linear time low tree-width partitions and algorithmic consequences, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Jaroslav Neetil , Patrice Ossona de Mendez, Tree-depth, subgraph coloring and homomorphism bounds, European Journal of Combinatorics, v.27 n.6, p.1022-1041, August 2006
D. Demaine , Fedor V. Fomin , Mohammadtaghi Hajiaghayi , Dimitrios M. Thilikos, Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs, Journal of the ACM (JACM), v.52 n.6, p.866-893, November 2005
vertex partitions;tree-width;edge partitions;small components