# Complexity of conditional colouring with given template.

1 Introduction

A k-colouring of a graph G is a partition of V(G) into k independent sets, some of which may be empty. Edges of G can have ends in any two different non-empty independent sets. A conditional k-colouring of G is also a partition of V(G), this time into k sets which satisfy some condition, that is, which each induce a subgraph belonging to some some family C [18]. Cells of the partition may be empty when C contains the null graph, [K.sub.0]. When C = {[[bar.K].sub.n] : n [greater than or equal to] 0}, the set of edgeless graphs, the definitions of conditional k-colouring and k-colouring coincide.

Homomorphisms provide another generalization of k-colouring. If H is a graph with vertex set {[v.sub.1], [v.sub.2], ..., [v.sub.k]}, then a homomorphism of G to H is an ordered partition ([V.sub.1], [V.sub.2], ..., [V.sub.k]) of V(G), with some cells allowed to be empty, such that an edge of G can have one end in [V.sub.i] and the other in [V.sub.j] only if [v.sub.i][v.sub.j] [member of] E(H). When H = [K.sub.k], a homomorphism of G to H is the same as a k-colouring of G.

A general framework that includes both conditional colourings and homomorphisms has been proposed [26]. Let H be a graph with vertex set {[v.sub.1], [v.sub.2], ..., [v.sub.k]}. A conditional colouring with condition C and template H, also known as an (H, C)-partition, is an ordered partition ([V.sub.1], [V.sub.2], ..., [V.sub.k]) of V(G) into sets which each induce a subgraph belonging to the family C, such that edge of G can have one end in Vi and the other in [V.sub.j] only if [v.sub.i][v.sub.j] [member of] E (H). Conditional k-colouring arises when the template H is chosen to be [K.sub.k], and homomorphism to H arises when C = {[[bar.K].sub.n] : n [greater than or equal to] 0}.

If C = {[[bar.K].sub.n] : n [greater than or equal to] 1}, then conditional colouring with condition C and template H becomes surjective homomorphism to H [17]. One can also impose the additional requirement that there be at least one edge of G with ends in different cells whenever these cells correspond to adjacent vertices of H. In this case, conditional colouring with condition C and template H becomes compaction to H [2, 27, 28, 29].

When C is the collection of non-null connected graphs, and it is required that there be an edge of G with ends in different cells whenever these cells correspond to adjacent vertices of H, then conditional colouring with condition C and template H becomes contractability to H [6, 24].

When H is a digraph and C is the collection of all acyclic digraphs, then conditional colouring with condition C and template H becomes acyclic homomorphism to H [15].

Dichotomy theorems provide a sharp dividing line between the situations where members of a class of problems can be solved in polynomial time and the situations where they are NP-complete. One example is k-colouring, where k is a fixed integer. The problem is Polynomial when k [less than or equal to] 2 and NP-complete when k [greater than or equal to] 3 [25]. Another example is homomorphism to the fixed graph H. The problem is Polynomial if H is bipartite or has a loop, and NP-complete when H is non-bipartite and has no loops [22].

Several dichotomy theorems are known for conditional colourings with condition C and template H. When C is the set of complete graphs, the problem is Polynomial if H is triangle-free and NP-complete if H has a triangle [26]. The statement does not change if [K.sub.0] is included in, or excluded from, C. The same theorem holds when C is the set of complete bipartite graphs or the set of stars. The polynomial algorithms all involve the same pre-processing phase, and similar reductions to 2-SAT. It is therefore natural to wonder for which classes C these techniques lead to a polynomial-time algorithm for conditional colouring with condition C and triangle-free template H. The primary focus of this paper is describe a very general collection of classes C where the methods succeed. It turns out to make no difference if different families are associated with different vertices of H. In some situations we are able to establish "complementary" NP-completeness results and similar dichotomy theorems as before. These results unify and extend previous work [26]. We also describe situations where H being triangle-free is not the dividing line between polynomiality and NP-completeness. Finally, we consider the variation of requiring there to be an edge of G with ends in different cells whenever these cells correspond to adjacent vertices of H.

There has been a wealth of previous work on conditional colouring problems. For a sample of older work, see [4, 5, 9, 20, 21]; for newer work see [1, 7, 8, 13, 12, 15, 16, 29]. Matrix partitions are a rich category of graph partitioning problems; see [19] for a survey. The input graph is partitioned into cells whose structure is determined by the entries of a given matrix M, as is the structure of the edges with ends in different cells. We borrow this idea to help describe our general collection of graph families in the next section.

The work of Farrugia (see [12, 13]) is of particular note. A condition is called additive if it contains [K.sub.0] and is closed under vertex-disjoint unions. He proved the conjecture of Kratochvil and Schiermeyer [23] that if P and Q are additive conditions, not both equal to the set of edgeless graphs, the problem of 2-colouring the vertices of a graph G so that the red vertices induce a graph in P and the blue vertices induce a graph in Q is NP-hard. When the conditions coincide, this implies that if C is additive and not the set of edgeless graphs, then conditional colouring with condition C and template K2 is NP-hard. By contrast, the conditions considered in this paper are not additive.

2 Starter-matrix classes

To motivate the graph classes introduced in this section we give an overview of the algorithm for conditional colouring with condition C and a triangle-free template H. We describe the algorithm in the case when C is the set of complete bipartite graphs with at least one edge. It is essentially unchanged if [K.sub.0] or [K.sub.1] is also included in C, or when C is the set of complete graphs, or the set of stars [26].

Given a graph G, the idea is to get the partition started, and then try to extend the partial partition to a partition of the desired type. Suppose V (H) = {[v.sub.1], [v.sub.2], ..., [v.sub.k]}. Each cell [V.sub.i] of the partition (corresponding to [v.sub.i]) is either empty, or contains a "starter" edge [a.sub.i][b.sub.i] to which all other vertices in the cell are adjacent.

The first step is to choose a starter edge for each cell. The number of ways to do this is bounded by the multinomial coefficient ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]), where n = [absolute value of V(G)]. Unless a partition is found, all possibilities will need to be checked before it can be asserted that there is no partition. Once the starter edges are selected, the next step is to check that if there are edges of G with ends in different cells, then these cells correspond to adjacent vertices of H. If this is false, move on to the next choice of starter edges. Assume, then, that each cell [V.sub.i] (so far) contains a starter edge [a.sub.i][b.sub.i], and edges of G with ends in different cells are permitted by adjacencies of the corresponding vertices in H.

Because the cells must each induce a complete bipartite graph, every vertex of G must be adjacent to an end of at least one starter edge. If this is false, move on to the next choice as before. Otherwise, let x be a vertex of G. If there is only one i such that N (x) [intersection] [V.sub.i] [not equal to] 0 then x must belong to [V.sub.i] in any extension of the starter edges to a partition of the desired type. Place x into Vi so long as the subgraph induced by Vi is complete bipartite; otherwise move on to the next choice. Similarly, since the template H is triangle-free, if x has neighbours in at least three cells Vi then the subgraph of H induced by the vertices corresponding to these cells must be a star, and x must belong to the cell corresponding to its centre. Place it there or move on, as before. The remaining possibility is that x has neighbours in exactly two cells [V.sub.i] and [V.sub.j] that correspond to adjacent vertices of H, and it must be decided where x is to be placed. The choice of the cell to which x is assigned depends on the choice of cell to which other vertices of G are assigned. The assignment can be made via a reduction to 2-SAT, as in the proof of Lemma 3.2 in the next section. For i < j and [v.sub.i][v.sub.j] [member of] E (H), let [E.sub.ij] be the set of vertices of G that must be placed in [V.sub.i] or [V.sub.j]. For each such vertex x, let s(x) be the statement "x can be placed in [V.sub.j]". The clauses fall into three main categories:

(i) Assure that if x is placed in [V.sub.i] or [V.sub.j] then the resulting induced subgraph is complete bipartite;

(ii) Assure that if x and y are both placed in the same cell then the resulting induced subgraph is complete bipartite;

(iii) Assure that there are edges of G with ends in different cells only when the cells correspond to adjacent vertices of H.

A satisfying truth assignment leads to an extension of the starter edges to conditional colouring with condition C and template H. If the clauses are not satisfiable, then we move on to the next choice. This can be determined in time linear in the number of clauses [10].

The main focus of this paper is to define a general collection of graph classes to which the method just described leads. The following is our definition of such a collection.

A starter-matrix class is a set C of graphs which is either empty or is defined by a triple (S, I, M), where

1. The starter graph S [member of] C, and is a labelled, induced subgraph of every element of C;

2. I is a set of non-empty subsets of V (S);

3. If G [member of] C and x [member of] V(G) - V(S), then [N.sub.G] (x) [intersection] V(S) [member of] I;

4. The rows and columns of the class structure matrix M are indexed by the elements of I;

5. Every entry of M is either 0, 1, or *;

6. For G [member of] C and any two vertices x, y [member of] V(G) - V(S), with NG (x) [intersection] V(S) = I [member of] I and [N.sub.G] (y) [intersection] V (S) = J [member of] I, we have

* if M (I, J) = 1, then xy [member of] E (G);

* if M (I, J) = 0, then xy [not equal to] E (G); and

* if M (I, J) = * then the vertices x and y may be either adjacent or non-adjacent.

Let C be a starter-matrix class defined by (S, I, M). For G [member of] C and X [member of] I, let [V.sub.X] be the set of vertices x [member of] V(G) - V (S) such that [N.sub.G] (x) [intersection] V (S) = X. Then the collection {[V.sub.X] : X [member of] I} [union] {V (S)} is a partition of V(G), and

* if M (I, J) = 1, then every vertex in [V.sub.I] is adjacent to every vertex in [V.sub.J];

* if M (I, J) = 0, then no vertex in [V.sub.I] is adjacent to a vertex in [V.sub.J]; and

* if M (I, J) = *, then there are no restrictions on adjacency between vertices in [V.sub.I] and [V.sub.J].

In particular, the (I, I) entry of the matrix M determines the structure of the subgraph of G induced by [V.sub.I]. It is complete when M (I, I) = 1, independent when M (I, I) = 0, and any graph at all when M (I, I) = *.

The matrix notation is taken from the area of matrix partitions [19]. We stress, however, that the meaning is different. In matrix partitions the matrix describes the structure of the cells of the partition and adjacencies between them. Here, it describes the structure of vertex sets with given neighbourhoods in the starter graph, and adjacencies between them. The partition does not need to be found; if it exists, it is determined by the elements of I.

The requirement in part 1 of the definition that S be a labelled, induced subgraph of every element of C can be relaxed to the requirement that S be a labelled subgraph of every element of C. We choose to not make this relaxation because nothing is added: an even greater level of generality is a consequence of Theorem 3.4.

We now give examples of some starter-matrix classes. Several of them make use of the generalized wreath product, which we now define. Let G be a (loopless) graph with vertex set {[x.sub.1], [x.sub.2], ..., [x.sub.n]}, and let [F.sub.1], [F.sub.2], ..., [F.sub.n] be mutually disjoint graphs. The generalized wreath product of G and [F.sub.1], [F.sub.2], ..., [F.sub.n] is the graph obtained by replacing each vertex [x.sub.i] by [F.sub.i], and joining every vertex of [F.sub.i] to every vertex of [F.sub.j] if and only if [x.sub.i][x.sub.j] [member of] E (G). That is, it is the graph with vertex set [U.sup.n.sub.i=1] {[x.sub.i]} x V ([F.sub.i]) and edge set {([x.sub.i],u) ([x.sub.j], v) : [x.sub.i][x.sub.j] [member of] E (G), u [member of] V ([F.sub.j]), v [member of] V ([F.sub.i])}. The generalized wreath product is also known as the generalized lexicographic product.

1. S = [K.sub.1], I = {{[s.sub.1]}}, and M = [1] gives the set of all (non-null) complete graphs;

2. S = [K.sub.1], I = {{[s.sub.1]}}, and M = [0] gives the set of all stars;

3. S = [K.sub.1], I = {{[s.sub.1]}}, and M = [*] gives the set of all graphs with a dominating vertex;

4. S = [K.sub.2], I = {{[s.sub.1]}, {[s.sub.2]}, {[s.sub.1], [s.sub.2]}}, and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

gives a graph of the form shown in Figure 1.

5. S is any fixed non-null graph, I = {[N.sub.S] (v) : v [member of] V(S)}, and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

gives the following set C of graphs. Let V (S) = {[x.sub.1], [x.sub.2], ..., [x.sub.v]}. A graph W belongs to C if and only if there exist positive integers [n.sub.1], [n.sub.2], ..., [n.sub.v] such that W is the generalized wreath product of S and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

6. S is any fixed graph, I = {[N.sub.S] [v] : v [member of] V(S)}, and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where N [x] = {x} [union] N (x), gives the following set C of graphs. Let V(S) = {[x.sub.1], [x.sub.2], ..., [x.sub.v]}. A graph W belongs to C if and only if there exist positive integers [n.sub.1], [n.sub.2], ..., [n.sub.v] such that W is the generalized wreath product of S and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

7. S = [[bar.K].sub.m], I the set of all non-empty subsets of V (S), and the matrix M having every entry equal to *, gives the set of all graphs with an independent dominating set of size m.

8. S = [P.sub.r] (the path of length r), I the set of all non-empty subsets of V (S), and the matrix M having every entry equal to * gives the set of graphs with a dominating induced path of length r.

In Example 8, the graph Pr can be replaced by any graph [G.sub.r] on r vertices. The starter matrix class is then the set of graphs with a dominating induced copy of [G.sub.r].

Starter-matrix classes include the families for which there are known polynomial algorithms when the template H is triangle-free. In Example 5 if S = [K.sub.m], then I is the set of all (m - 1)-subsets of V (S), and C is the set of all complete m-partite graphs. With m = 2 this is the set of all complete bipartite graphs. Similarly, in Example 6, if S = [K.sub.1], then C is the set of all cliques.

The starter graph S is important in the sense that its vertices form a dominating set for any graph in the class. Hence the set of edgeless graphs (independent sets) is not a starter-matrix class. Our results do not apply to k-colouring or homomorphism to H.

Proposition 2.1 Let the starter-matrix class C be defined by the triple (S, I, M). There is a polynomial-time algorithm to test membership in C.

Proof: Suppose an input graph G is given. Since S is fixed, there are polynomially many [absolute value of V (S)]-- subsets X [subset or equal to] V(G), and for each of them we can test whether the induced subgraph is isomorphic to S in constant time. Further, [absolute value of V (S)]!, the number of possible isomorphisms of G[X] to S is a constant.

Perform the following checks for each X [subset or equal to] V(G) such that G[X] [congruent to] S and for each isomorphism of G[X] to S, stopping if it has been verified that G [member of] C. If all possibilities are checked and none verifies that G [member of] C, then G [not member of] C.

Suppose that G[X] [congruent to] S, and that the vertices of G[X] are labelled by an isomorphism to S. In what follows we refer to G[X] as S. First check that for each vertex w [member of] V(G) - V (S) we have [N.sub.G] (w) [intersection] V (S) [member of] I. If this property holds for each vertex w [member of] V(G) - V (S), then generate the partition {[V.sub.I] : I [member of] I} of V(G) - V (S). For all I, J [member of] I, check if the requirements specified by M are met. Each of these checks can clearly be accomplished in polynomial time. If G passes each check, then G [member of] C.

3 Triangle-Free Graphs

The results in this section are not further complicated by allowing a starter-matrix class [C.sub.v] to be associated with each vertex of H, rather than assuming the same class C is associated with each vertex of H. We shall refer to this more general problem as conditional colouring with conditions [C.sub.v] and template H. The purpose of this section is to describe a polynomial-time algorithm for the conditional colouring with conditions [C.sub.v] and template H when the template graph H is triangle-free and each family [C.sub.v], v [member of] V (H), is a starter-matrix class. Suppose [C.sub.v], v [member of] V (H), if it is non-empty, is defined by ([S.sub.v], [I.sub.v], [M.sub.v]).

The main idea of the algorithm is as described before: find the vertex sets of the starter graphs and then a partition of the remaining vertices so that the requirements prescribed by H and class structure matrices are met. Suppose X = {[X.sub.v] : v [member of] V (H)} is a collection of disjoint subsets of V(G) acting as the vertex sets of the starter graphs [S.sub.v], v [member of] V (H), respectively. A partition P = {[P.sub.v] : v [member of] V (H)} of the vertices of G - [U.sub.v [member of] V(H)][X.sub.v] so that the requirements prescribed by H and class structure matrices [M.sub.v], v [member of] V (H), are met is called an extension of X. If one of these exists, we say that the collection X is extendable.

Proposition 3.1 Let G be an instance of the conditional colouring with conditions [C.sub.v] and template H, where the template graph H is triangle-free and each family [C.sub.v], v [member of] V (H), is a starter-matrix class. IfX = {[X.sub.v] : v [member of] V (H)} is an extendable collection of disjoint subsets of V(G) acting as the vertex sets of the starter graphs [S.sub.v], v [member of] V (H), respectively, then every vertex x [member of] V(G) - [[union].sub.v [member of] V(H)] [X.sub.v] has neighbours in:

(a) exactly one set [X.sub.v];

(b) exactly two sets [X.sub.v], [X.sub.w] that correspond to adjacent vertices of H; or

(c) at least three starter graphs corresponding to an induced star in H;

Proof: Since each family [C.sub.v], v [member of] V (H), is a starter-matrix class, every vertex x [member of] V(G) - [[union].sub.v[member of]V(H)] [X.sub.v] must have a neighbour in some set [X.sub.v]. The conditions (a), (b), (c) are straightforward from the requirements specified by the template H.

The three possibilites for neighbours of a vertex x [member of] V(G) - [[union].sub.v[member of]V(H)] [X.sub.v] help determine the part to which x must belong in any extension. In the case (a) it is clear to which part the vertex x must belong. The same is true in case (c): in order to meet the requirements prescribed by H it must belong to the part corresponding to the centre vertex of the star. Only in the second case must a decision be made.

We define a potential start structure to be a collection of (mutually) disjoint subsets X = {[X.sub.v] : v [member of] V(H)} such that

1. G[[X.sub.v]] [congruent to] [S.sub.v], v [member of] V (H), and there is an edge with ends in different sets only when these sets correspond to adjacent vertices of H;

2. the vertices in each set [X.sub.v] are labelled according to an isomorphism from G[[X.sub.v]] to [S.sub.v];

3. each vertex of G - [[union].sub.v[member of]V(H)] [X.sub.v] has neighbours in:

(a) exactly one starter graph;

(b) exactly two starter graphs that correspond to adjacent vertices of H; or

(c) at least three starter graphs corresponding to an induced star in H.

As in the proof of Proposition 2.1, it may be that, ultimately, all possibilities for the collection of sets [X.sub.v] and associated isomorphisms need to be examined. Fortunately, there are a polynomial number of such possibilities.

Lemma 3.2 Let G be an instance of conditional colouring with conditions [C.sub.v] and template H, where the template graph H is triangle-free and each family [C.sub.v], v [member of] V (H), is a starter-matrix class. Then, there is a polynomial-time algorithm that determines ifa potential start structure X = {[X.sub.v] : v [member of] V (H)} is extendable.

Proof: Suppose [C.sub.v], v [member of] V (H), is defined by ([S.sub.v], [I.sub.v], [M.sub.v]). In the sequel we shall refer to G[[X.sub.v]] as [S.sub.v].

We first build the sets [P.sub.v], v [member of] V (H), the vertices forced to belong to it in any extension. These are determined by cases (a) and (c) of Proposition 3.1. Any such vertex x must have [N.sub.G] (x) [intersection] V ([S.sub.v]) [member of] I or there is no extension. Further, x can only be added to [P.sub.v] if all requirements specified by the class structure matrix M are met. The checks required to carry out this step can be carried out in polynomial time.

At this point, each vertex x [member of] V(G)- [[union].sub.v[member of]V(H)] ([X.sub.v] [union] [P.sub.v]) has neighbours inexactly two sets [X.sub.i], [X.sub.j] that correspond to adjacent vertices of H. We use [E.sub.ij], i < j to denote the set of all vertices with neighbours in both [X.sub.i] and [X.sub.j]. These sets partition V(G) - [[union].sub.v[member of]V(H)]([X.sub.v] [union] [P.sub.v]). The test for extendability is completed using a reduction to 2-SAT. For each vertex x [member of] V(G) - [[union].sub.v[member of]V(H)] ([X.sub.v] [union] [P.sub.v]) there is a Boolean variable which, for simplicity, we will also denote by x. The clauses fall into several groups, as described below. The idea behind the clauses is that if the variable x has truth value 0 (false), then to form the partition sought the vertex x will eventually be added to [P.sub.i], and if x has truth value 1 (true) then it will eventually be added to [P.sub.j].

FD (Forced Decisions). The purpose of these clauses is to take care of the situations where x [member of] [E.sub.ij] can not be added to [P.sub.i] or [P.sub.j] because the resulting subgraph does not belong to [C.sub.i] or [C.sub.j], respectively.

* FD1: {[bar.x] : x [member of] [E.sub.ij], G[[X.sub.j] [union] [P.sub.j] [union] {x}] [not member of] [C.sub.j]}

* FD2: {x : x [member of] [E.sub.ij], G[[X.sub.i] [union] [P.sub.i] [union] {x}] [not member of] [C.sub.i]}

KA (Keep Apart). The purpose of these clauses is to take care of situations where two vertices x, y can not both added to the same set because the resulting subgraph does not belong to [C.sub.i] or [C.sub.j], respectively. The algorithm from Proposition 2.1 is used to generate these clauses.

* KA1: {x [disjunction] y : x, y [member of] [E.sub.ij], G[[X.sub.i] [union] [P.sub.i] [union] {x, y}] [not member of] [C.sub.i]}

* KA2: {[bar.x] [disjunction] [bar.y] : x, y [member of] [E.sub.ij], G[[X.sub.j] [union] [P.sub.j] [union] {x, y}] [not member of] [C.sub.j]}

* KA3: {[bar.x] [disjunction] y : x [member of] [E.sub.ij], y [member of] [E.sub.jl], G[[X.sub.j] [union] [P.sub.j] [union] {x, y}] [not member of] [C.sub.j]}

* KA4: {x [disjunction] y : x [member of] [E.sub.ij], y [member of] [E.sub.il], G[[X.sub.i] [union] [P.sub.i] [union] {x, y}] [not member of] [C.sub.i]}

* KA5: {[bar.x] [disjunction] [bar.y] : x [member of] [E.sub.ij], y [member of] [E.sub.lj], G[[X.sub.j] [union] [P.sub.j] [union] {x, y}] [not member of] [C.sub.j]}

TF (Triangle Free). The purpose of these clauses is to assure the restrictions on adjacency specified by the template H being triangle-free are respected when adding vertices to different parts: if ij, jl [member of] E (H) then il [not member of] E (H).

* TF1: {x [disjunction] [bar.y] : x [member of] [E.sub.ij], y [member of] [E.sub.jl], xy [member of] E(G)}

* TF2: {[bar.x] [disjunction] [bar.y] : x [member of] [E.sub.ij], y [member of] [E.sub.il], xy [member of] E(G)}

* TF3: {x [disjunction] y : x [member of] [E.sub.ij], y [member of] [E.sub.lj], xy [member of] E(G)}

FE (Forbidden Edges). The purpose of these clauses is to assure the restrictions on adjacency specified by the edges of the template H are respected when adding vertices to different parts. If x [member of] [E.sub.ij] and y [member of] [E.sub.rs] with i, j [not member of] {r, s}, then the placement of x and y into parts must respect the edges of H with one end in {i, j} and the other end in {r, s}.

* FE1. {x [disjunction] [bar.y], [bar.x] [disjunction] y : xy [member of] E (G), x [member of] [E.sub.ij], y [member of] [E.sub.rs], i,j [not member of] {r,s}, ir, js [member of] E (H)}

* FE2. {[bar.x], [bar.y] : xy [member of] E (G), x [member of] [E.sub.ij], y [member of] [E.sub.rs], i, j [not member of] {r, s}, ir [member of] E (H), js [not member of] E (H)}

* FE3. {x, y : xy [member of] E (G), x [member of] [E.sub.ij], y [member of] [E.sub.rs], i, j [not member of] {r, s}, ir [not member of] E (H), js [member of] E (H)}

* FE4. {x [disjunction] y, [bar.x] [disjunction] [bar.y] : xy [member of] E (G), x [member of] [E.sub.ij], y [member of] [E.sub.rs], i,j [not member of] {r,s}, is, jr [member of] E (H)}

* FE5. {x, y : xy [member of] E(G), x [member of] [E.sub.ij], y [member of] [E.sub.rs], i, j [not member of] {r, s}, is [member of] E (H), jr [not member of] E (H)}

* FE6. {[bar.x], y : xy [member of] E (G), x [member of] [E.sub.ij], y [member of] [E.sub.rs], i, j [not member of] {r, s}, is [not member of] E (H), jr [member of] E(H)}

By Proposition 2.1, the collection of clauses can be generated in polynomial time. A satisfying truth assignment, or a certificate that no such truth assignment exists can found be in linear time [10].

Suppose the collection of clauses above has a satisfying truth assignment. As alluded above, for x [member of] [E.sub.ij], i < j, put x in [P.sub.i] when the variable x is false, and in Pj when it is true. We claim that the collection {[X.sub.v] [union] [P.sub.v] : v [member of] V (H)} is a partition of the desired type. Since all clauses in "Forced Decisions" are true, every vertex of [P.sub.i] is adjacent to [S.sub.i] in accordance to [M.sub.i] (and [I.sub.i]). All clauses in "Keep Apart" being true enforce that vertices x and y that together cannot belong to the same part are kept apart. Thus the first seven clauses groups being satisfied imply that the requirements specified by the collections [C.sub.v], v [member of] V(H), are met. It remains to argue that the structure specified by the template H is respected. The clause groups "Triangle Free" and "Forbidden Edges" enforce that adjacent vertices of G are placed into parts corresponding to adjacent vertices of H. (See Figures 2 and 3.) This proves the claim.

Conversely, suppose X has an extension P. As before if x [member of] [E.sub.ij], i < j, then in any extension either x [member of] [P.sub.i] or x [member of] [P.sub.j]. Set the variable x to false if x [member of] [P.sub.i], and to true if x [member of] [P.sub.j]. It is easy to check that the clauses are satisfied.

The proof is complete on noting that each of the required checks can be carried out in polynomial time.

Theorem 3.3 If H is a triangle-free graph and each [C.sub.v], v [member of] V (H), is a starter-matrix class, then conditional colouring with conditions [C.sub.v] and template H is polynomial.

Proof: Let | V(G) | = n. Apply the following to the subgraph H' of H induced by the set vertices v such that [C.sub.v] [not equal to] 0.

Let V (H') = {1, 2, ..., h'} and, for v [member of] V (H'), [absolute value of [S.sub.v]] = [s.sub.v]. The number of potential start structures is polynomial: the number of possible choices for the collection X = {[X.sub.v] : v [member of] V (H)} is the multinomial coefficient

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

Except for n, all numbers involved in the expression are constants. To make a potential start structure an isomorphism from each graph G[[X.sub.v]] to [S.sub.v] must be specified. Thus, each collection X gives rise to at most the constant number [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of potential start structures. It now follows from Lemma 3.2 that conditional colouring with template H' and conditions [C.sub.v].

This completes the proof.

Because of the generality, the time complexity of the algorithms is astronomical (especially the size of the constants), though polynomial because the template H and classes [C.sub.v] are all fixed. Far more efficient algorithms are no doubt possible if one focusses on specific problems. For example, when H = [C.sub.4] and C is the set of cliques, our algorithm has time complexity O ([n.sup.6]), where n = V(G), whereas a specific algorithm due to Everett, Klein and Reed [11] has time complexity O (n + m), where m = [absolute value of E(G)].

It turns out to make no significant difference, other than to the constants involved in the proof of Theorem 3.3, if each vertex of H has associated with it a finite collection of starter-matrix classes. In particular, this allows for cells to be either empty or to induce a subgraph belonging to a given collection [26]. We therefore obtain the following, for which the proof is straightforward and omitted.

Theorem 3.4 If H is a triangle-free graph and each [C.sub.v], v [member of] V (H), is a union of finitely many starter- matrix classes, then conditional colouring with conditions [C.sub.v] and template H is polynomial.

One consequence of the above theorem is that the restriction, in part 1 of the definition of a starter-matrix class C, that S be a labelled, induced subgraph of each element of C can be relaxed to S being a labelled subgraph of every graph in the collection: take the union of the starter-matrix classes such that S is a spanning subgraph of the starter graph for the class. Much more generality is clearly available from the theorem, however.

4 Dichotomy Theorems

We now prove that H having a triangle is the "dividing line" for NP-completeness of some large classes of conditional colouring problems with starter-matrix condition C and template H. We stress here that starter-matrix classes originated from trying to find polynomial algorithms for conditional colouring problems with given template. Finding general NP-complete results seems to be difficult when different classes can be associated with different vertices of H. Hence we will focus on the situation where the same condition is associated with all vertices of H. Previous dichotomy theorems of this form all involve situations where C is a starter matrix-class defined by (S, I, M), where I is inclusion-free and M has all diagonal entries equal to zero (stars, complete bipartite graphs) or one (complete graphs) [26]. The two main results in this section generalize these.

For a given graph G, a conditional colouring with condition C and template H can be described by giving the partition of V(G). Once can verify that a given partition is such a conditional colouring by checking that the subgraph induced by each cell belongs to C and there is an edge with ends in different cells only when these cells correspond to adjacent vertices of H. Hence:

Observation 4.1 If membership in C can be checked in polynomial time, then conditional colouring with condition C and template H is in NP.

Corollary 4.2 If C is a union of finitely many starter-matrix classes, then conditional colouring with condition C and template H is in NP.

The next two theorems involve situations where the class structure matrix M has all diagonal entries equal to zero, and where it has all diagonal entries equal to one. Since these symbols represent complementary structures, it is not surprising that the proofs are strongly similar.

Theorem 4.3 Suppose that C is a non-empty starter-matrix class defined by (S, I, M) such that every diagonal entry of M equals zero, and I is inclusion-free. If H is triangle-free, then conditional colouring with condition C and template H is Polynomial. If H has a triangle, then conditional colouring with condition C and template H is NP-complete.

Proof: Because of Theorem 3.3, it remains to prove the statement about NP-completeness. Membership in NP was established in Corollary 4.2. The transformation is from H-colouring. Suppose an instance, G, of H-colouring is given. We shall construct a graph G' such that G' has a conditional colouring with condition C and template H if and only if G admits a homomorphism to H.

Let V (H) = {[[alpha].sub.1], [[alpha].sub.2], ..., [[alpha].sub.h]}, and I [member of] I. The construction begins with h disjoint labelled copies of S, say [S.sub.1], [S.sub.2], ..., [S.sub.h], and the wreath product, W, of G with an edgeless graph (that is, an independent set) on h * [absolute value of V(S)] + 1 vertices. For i = 1, 2, ..., h, let [I.sub.i] be the subset of V ([S.sub.i] corresponding to I. The graph G' is constructed from the disjoint union of [S.sub.1], [S.sub.2], ..., [S.sub.h] and F by joining every vertex of F to every vertex of [I.sub.1] [union] [I.sub.2] [union] ... [union] [I.sub.h]. The construction can clearly be accomplished in polynomial time. We show that G has a homomorphism to H if and only if G' has a conditional colouring with condition C and template H.

Suppose G has a homomorphism to H, that is, a conditional colouring with condition {[bar.[K.sub.n]] : n [greater than or equal to] 0} and template H, say ([P.sub.1], [P.sub.2], ..., [P.sub.h]). Then, from the definition of wreath product, F also has such a conditional colouring with template H, say ([Q.sub.1], [Q.sub.2], ..., [Q.sub.h]). It follows that (V ([S.sub.1]) [union] [Q.sub.1], V ([S.sub.2]) [union] [Q.sub.2], ..., V ([S.sub.h]) [union] [Q.sub.h]) is the desired partition of G'.

Suppose G' has a conditional colouring with condition C and template H, say ([P.sub.1], [P.sub.2], ..., [P.sub.h]). Each set [P.sub.i] contains a subset [V.sub.i] for which the induced subgraph is the required labelled copy [S.sub.i] of S. By the Pigeonhole Principle, at least one vertex of each large independent set that replaced a vertex of G is not in [V.sub.1] [union] [V.sub.2] [union] *** [union] [V.sub.h]. Since the subgraph of F induced by any set of vertices containing exactly one from each of these independent sets is isomorphic to G, there is a copy [G.sub.1] of G whose vertices do not belong to any of the starter graphs. If [P.sub.i] [intersection] V ([G.sub.1]) [not equal to] 0, then all vertices in [P.sub.i] [intersection] V ([G.sub.1]) are adjacent to exactly the same vertices in [V.sub.i]. Since I is inclusion-free and every diagonal entry of M equals 1, the subgraph of [G.sub.1] induced by [P.sub.i] [intersection] V ([G.sub.1]) is complete. Hence ([P.sub.1] [intersection] V ([G.sub.1]), [P.sub.2] [intersection] V ([G.sub.1]), ..., Ph n V (G1)) corresponds to the desired partition of G.

Recalling the earlier examples, we note a few consequences of Theorem 4.3.

Corollary 4.4 [26] Let C be the set of complete bipartite graphs. If H is triangle-free, then conditional colouring with condition C and template H is Polynomial. If H contains a triangle, then conditional colouring with condition C and template H is NP-complete.

Corollary 4.5 [26] Let C be the set of stars. If H is triangle-free, then conditional colouring with condition C and template H is Polynomial. If H contains a triangle, then conditional colouring with condition C and template H is NP-complete.

Corollary 4.6 Let C be the set of complete multipartite graphs. If H is triangle-free, then conditional colouring with condition C and template H is Polynomial. If H contains a triangle, then conditional colouring with condition C and template H is NP-complete.

Theorem 4.7 Suppose that C is a non-empty starter-matrix class defined by (S, I, M) such that every diagonal entry of M equals one, and I is inclusion-free. If H is triangle-free, then conditional colouring with condition C and template H is Polynomial. If H has a triangle, then conditional colouring with condition C and template H is NP-complete.

Proof: Because of Theorem 3.3, it remains to prove the statement about NP-completeness. Membership in NP was established in Corollary 4.2. It remains to get a reduction.

Recall the problem of partitioning into cliques with template H (see [26]), also called (H, C)-partition, where C is the set of (non-null) complete graphs. Suppose an instance of this problem, a graph G, is given. Construct an instance G' of conditional colouring with condition C and template H as follows.

Let V(H) = {[[alpha].sub.1], [[alpha].sub.1], ..., [[alpha].sub.h]}, and I [member of] I. The construction begins with h disjoint labelled copies of S, say [S.sub.1], [S.sub.2], ..., [S.sub.h], and the wreath product, W, of G and a complete graph on h * [absolute value of V(S)] + 1 vertices. For i = 1, 2, ..., h, let [I.sub.i] be the subset of V ([S.sub.i]) corresponding to I. The graph G' is constructed from the disjoint union of [S.sub.1], [S.sub.2], ..., [S.sub.h] and F by joining every vertex of F to every vertex of [I.sub.1] [union] [I.sub.2] [union] *** [union] [I.sub.h]. The construction can clearly be accomplished in polynomial time. We show that G has a partition into cliques with template H if and only if G' has a conditional colouring with condition C and template H.

Suppose G has a partition into cliques with template H, say ([P.sub.1], [P.sub.2], ..., [P.sub.h]). Then, from the definition of wreath product, F also has a partition into cliques with template H, say ([Q.sub.1], [Q.sub.2], ..., [Q.sub.h]). It follows that (V ([S.sub.1]) [union] [Q.sub.1], ..., V ([S.sub.h]) [union] [Q.sub.h]) is the desired partition of G'.

Suppose G' has a conditional colouring with condition C and template H, say ([P.sub.1], [P.sub.2], ..., [P.sub.h]). Each set [P.sub.i] contains a subset Vi for which the induced subgraph is the required labelled copy [S.sub.i] of S. By the Pigeonhole Principle, at least one vertex of each large complete graph that replaced a vertex of G is not in [V.sub.1] [union] [V.sub.2] [union] ... [union] [V.sub.h]. Since the subgraph of F induced by any set of vertices containing exactly one from each of these complete graphs is isomorphic to G, there is a copy [G.sub.1] of G whose vertices do not belong to any of the starter graphs. If [P.sub.i] [intersection] V ([G.sub.1]) [not equal to] 0, then all vertices in [P.sub.i] [intersection] V ([G.sub.1]) are adjacent to exactly the same vertices in [V.sub.i]. Since I is inclusion-free and every diagonal entry of M equals 1, the subgraph of [G.sub.1] induced by [P.sub.i] [intersection] V ([G.sub.1]) is complete. Hence ([P.sub.1] [intersection] V ([G.sub.1]), [P.sub.2] [intersection] V ([G.sub.1]), ..., [P.sub.h] [intersection] V ([G.sub.1])) corresponds to the desired partition of G.

5 Diagonal stars: the role of domination

We saw in Theorem 3.3 that conditional colouring with condition C and template H is Polynomial for any triangle-free graph H and starter-matrix class C. Based on the results in Section 4, it is tempting to conjecture that any such problem is NP-complete when H contains a triangle. In this section we show that this assertion is false in general when the class-structure matrix M can have diagonal entries equal to *.

Informally, the join of two disjoint graphs G and H is the graph constructed from the disjoint union of G and H by adding edges joining every vertex of G to every vertex of H. Formally, it is the graph G V H with vertex set V(G) [union] V (H) and edge set E (G) [union] E (H) [union] {gh : g [member of] V(G), h [member of] V (H)}. If either G or H has at least two vertices, then G V H has a triangle. If G, say, is empty then G V H = H.

Theorem 5.1 For a fixed integer n [greater than or equal to] 1, let F be a triangle-free graph, and H = F V [K.sub.n]. Suppose that the non-empty starter-matrix class C is defined by (S, I, M), where I is the set of all non-empty subsets of V (S) and every diagonal entry of M equals *. Then conditional colouring with condition C and template H is polynomial.

Proof: Suppose X = ({[X.sub.v]} : v [member of] V (H)) is a potential start structure. By definition of H, any vertex of G not in [U.sub.v[member of]V(H)] [X.sub.v] which is adjacent to a vertex in a starter graph corresponding to a vertex w of [K.sub.n] can be assumed to belong the cell corresponding to w in a partition of the required type. Let G' be the subgraph of G induced by the vertices in X' = ({[X.sub.v]} : v [member of] V (F)) and the vertices of G not adjacent to any vertex in [U.sub.v[member of]V(H)] [X.sub.v]. The graph G has a conditional colouring with condition C and template H if and only if X' is an extendable potential start structure for conditional colouring with condition C and template F.

There are polynomially many possibilities for X. For each of these, the graph G' can be found in polynomial time and extendability can be determined in polynomial time. The result now follows.

Recall from Section 2 that each of the following is a starter-matrix class that satisfies the hypotheses of Theorem 5.1.

* The set [D.sub.m] of graphs with an independent dominating set of size m [greater than or equal to] 1 (Examples 3 and 7);

* The set [B.sub.r] of graphs with a dominating induced path of length r [greater than or equal to] 0. (Example 8).

Corollary 5.2 For a fixed integer n [greater than or equal to] 1, let F be a triangle-free graph, and H = F V [K.sub.n]. For any m [greater than or equal to] 1, conditional colouring with condition [D.sub.m] and template H is Polynomial.

Corollary 5.3 For a fixed integer n [greater than or equal to] 1, let F be a triangle-free graph, and H = F V [K.sub.n]. For any r [greater than or equal to] 1, conditional colouring with condition Br and template H is Polynomial.

It is clear that Corollary 5.3 holds when the starter graph Pr is replaced by any fixed graph on r vertices. Together with Theorem 3.4, this implies the following, in which the condition can informally be described as "has a connected dominating set of size r".

Corollary 5.4 Let C be the union of all starter-matrix classes (S, I, M) where S is a connected graph on r vertices, I is the set of all non-empty subsets of V (S) and every entry of M equals *. For a fixed integer n [greater than or equal to] 1, let F be a triangle-free graph, and H = F V [K.sub.n]. For any r [greater than or equal to] 1, conditional colouring with condition C and template [K.sub.n] is Polynomial.

We now show that there are graphs H for which conditional colouring with condition [D.sub.1] and template H is NP-complete. In what follows, we will make use of the result that (n - 1)--colouring remains NP-complete when the input is restricted to graphs that admit an n-colouring [3].

Theorem 5.5 For n [greater than or equal to] 4, let H be the complete multipartite graph H = [K.sub.n, n, ..., n], with n - l parts of size n. Then conditional colouring with condition D1 and template H is NP-complete, even when the restricted to n-colourable graphs.

Proof: Let the defining independent sets of H be [V.sub.i] = {[v.sub.i,1], ..., [v.sub.i,n]} for i = l, ..., n - l.

The transformation is from (n - 1)--colouring restricted to n-colourable graphs. Suppose an instance of this problem, a graph G and an n-colouring c : V(G)--{1, 2, ..., n}, are given.

Construct a graph G' from G [union] H by joining x [member of] V(G) to [v.sub.i,c(x)] for i = 1, 2, ..., n - 1 and then, for each vertex [v.sub.i,j] [member of] V(H) adding two new vertices [y.sub.i,j], [z.sub.i,j] and joining them to [v.sub.i,j]. The construction can clearly be carried out in polynomial time. We claim that G is (n - l)--colourable if and only if G' has an (H, {[C.sub.i]})--partition.

Let f : V(G) [right arrow] {1, 2, ..., n - 1} be an (n - 1)-colouring of G. The collection X is the collection of singleton subsets of the vertices of the copy of H in G'. Put each vertex x of the copy of G in G' into the cell corresponding to [v.sub.f(x),c(x)], along with the vertices [y.sub.i,j], [z.sub.i,j]. Note that if xy [member of] E(G) we have f (x) [not equal to] f (y) and c (x) [not equal to] c (y), so that [v.sub.f(x),c(x)] is adjacent to [v.sub.f(y),c(y)], so that the required partition has been produced.

Conversely, suppose G' has a conditional colouring with condition D1 and template H. The presence of the vertices [y.sub.i,j], [z.sub.i,j] adjacent only to [v.sub.i,j] implies that the vertices [v.sub.i,j] are the dominating vertices for the cells of the partition. Define a (n - 1)-colouring f : V(G) [right arrow] {1, 2, ..., n - 1} by f (x) = i if and only if x belongs to the part of the partition corresponding to [v.sub.i,c(x)]. Because of the properties of H and c, the set [f.sup.-1] is independent.

In problems like contractibility to H, surjective homomorphism to H, and compaction to H, the input graph G is partitioned into cells such that there is an edge of G with its ends in different cells for any two cells that correspond to adjacent vertices of H. Even though none of these problems involve a startermatrix class of graphs, they suggest the natural question of whether our results extend to the situations where it is required that, in a conditional colouring with template H, some edge of the input graph G has ends in different cells of the partition whenever these cells correspond to adjacent vertices of H. We argue that they do.

Theorems 3.4 and 5.1 still hold. It is clear that if the edges with ends in different cells can be seen as edges joining vertices of the starter graphs, then the requirement can be built into the definition of a potential start structure. If this is not so, then the starter matrix class C defined by (S, I, M) can be replaced by a union of 1 + [absolute value of I] starter-matrix classes: C and, for I [member of] I the class defined by ([S.sub.I], I, M) where [S.sub.I] is the graph constructed from the disjoint union S [union] {x} by joining x to all vertices in I.

We note that the proofs of Theorems 4.3 and 4.7 are unchanged if a collection of edges corresponding to those of H are inserted between the copies of S in the construction.

7 Concluding Remarks

By Theorem 3.4, conditional colouring with a starter-matrix condition and a triangle-free template remains Polynomial if some cells are allowed to be empty. Correspondingly, the proofs of Theorems 4.3 and 4.7 do not rely on all cells of the partition being non-empty. Hence the same dichotomy theorems hold whether or not cells are allowed to be empty, and whether or not there is required to be an edge with ends in different non-empty cells whenever they correspond to adjacent vertices of H.

Finally, we note that the situations in which dichotomy theorems have been found, and the "dividing line" is the template graph H having a triangle, the class structure matrix had all diagonal entries equal to zero, or all diagonal entries equal to one. We wonder whether this holds in general. When the class structure matrix has all diagonal entries equal to "*" the dividing line, if there is one, is somewhere else.

Acknowledgements

The authors would like to thank the anonymous referees for their careful reading which helped improve the manuscript.

References

[1] V. Alekseev, A. Farrugia and V. Lozin, New results on generalized graph coloring. Discrete Math. Theor. Comput. Sci. 6 (2004), 215-221.

[2] M. Bodirsky, J. Kara and B. Martin, The complexity of surjective homomorphism problems--A survey. Discrete Applied Mathematics, 160 (2012), 1680-1690.

[3] R. C. Brewster, P. Hell and G. MacGillivray, The complexity of restricted graph homomorphisms. Discrete Math. 167/168 (1997), 145-154.

[4] I. Broere and C.M. Mynhardt, Generalized colourings of graphs. In Y. Alavi et al. eds. Graph Theory with Applications to Algorithms and Computer Science, John Wiley & Sons, New York, 1985, 583-594.

[5] J. Brown and D. G. Corneil, On generalized graph colourings. J. Graph Theory 11 (1987), 87-99.

[6] A. E. Brouwer, and H. Veldman, Contractibility and NP-completeness. J. of Graph Theory 11 (1987), 71-79.

[7] G. Chartrand, H. Hevia and O. Oellermann, On m-chromatic factorizations of complete graphs. J. Combin. Math. Combin. Comput. 47 (2003), 3-17.

[8] R. Churchley and J. Huang, List monopolar partitions of claw-free graphs. Discrete Math. 312 (2012), 2545-2549.

[9] G. Cornuejols, D. Hartvigsen, and W. Pulleyblank, Packing subgraphs in a graph. OR Letters 4 (1982), 139-143.

[10] S. Even, A. Itai and A. Shamir, On the complexity of timetable and multicommodity flow problems. SIAM J. Computing 5 (1976), 691-703.

[11] H. Everett, S. Klein and B. Reed, An optimal algorithm for finding clique-cross partitions. Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1998). Congr. Numer. 135 (1998), 171-177.

[12] A. Farrugia, Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. Electron. J. Combin. 11 (2004), no. 1, Research Paper 46.

[13] A. Farrugia, P. Mihok, R.B. Richter and G. Semanivin, Factorizations and characterizations of inducedhereditary and compositive properties. J. Graph Theory 49 (2005), 11-27.

[14] T. Feder, P. Hell, S. Klein and R. Motwani, List Partitions. SIAM J. Discrete Math. 16 (2003), 449-478.

[15] T. Feder, P. Hell and B. Mohar, Acyclic homomorphisms and circular colorings of digraphs. SIAM J. Discrete Math. 17 (2003), 161-169.

[16] J. Gimbel, and J. Nesetril, Partitions of graphs into cographs. Discrete Math. 310 (2010), 3437-3445.

[17] P.A. Golovach, B. Lidicky, B. Martin and D. Paulusma. Finding vertex-surjective graph homomorphisms. Acta Inform. 49 (2012), 381-394.

[18] F. Harary, Conditional colorability in graphs. Graphs and Applications, Proceedings of the 1st Colorado Symposium on Graph Theory, F. Harary and J. Maybee, eds., Wiley, New York, (1985), 127-136.

[19] P. Hell, Graph partitions with prescribed patterns. European J. Combin. 35 (2014), 335-353.

[20] P. Hell, and D. G. Kirkpatrick, On the complexity of general graph factor problems. SIAM J. Computing 12 (1983), 601-609.

[21] P. Hell, D. G. Kirkpatrick, J. Kratochvfl, and I. KHz, On restricted two-factors. SIAMJ. Discrete Math. 1 (1988), 472-484.

[22] P. Hell and J. Nesetril, On the complexity of H-colouring. J. Comb. Theory, Ser. B 48 (1990), 92-110.

[23] J. Kratochvil and I. Schiermeyer, On the computational complexity of (O,P)--partition problems. Discuss. Math. Graph Theory 17 (1997), 253-258.

[24] A. Levin, D. Paulusma and G. Woeginger, The Computational Complexity of Graph Contractions I: Polynomially Solvable and NP-Complete Cases. Networks, 51 (2008), 178-189.

[25] L. Lovasz, Coverings and coloring of hypergraphs, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math., Winnipeg, Man., 1973, 3-12.

[26] G. MacGillivray and M-L. Yu, Generalized graph partitioning problems. Discrete Applied Mathematics 91 (1999), 143-153.

[27] N. Vikas, Algorithms for partition of some class of graphs under compaction. Computing and combinatorics, 319-330, Lecture Notes in Comput. Sci., 6842, Springer, Heidelberg, 2011.

[28] N. Vikas, Compaction, retraction, and constraint satisfaction. SIAM J. Comput. 33 (2004), 761-782.

[29] N. Vikas, Computational complexity of graph compaction. Ph.D. Thesis, Simon Fraser University (Canada). 1997.

Peter J. Dukes *

Steve Lowdon

Gary MacGillivray ([dagger])

Mathematics and Statistics, University of Victoria, Canada

received 14th Nov. 2012, revised 12th Apr 2014, accepted 5th June 2014.

* Email: dukes@uvic.ca.

([dagger]) Research of the authors is supported by NSERC.